f****r
发帖数: 30 | 1 去google interview的同学们， 有人被要求过2nd onsite吗? 今天recruiter打电话说
上次（3weeks ago）的onsite不能move on, 要再给一次onsite (2-3people)。谁有经
验的给说说？ 谢谢了 |
h*********3
发帖数: 111 | 2 我听说个一个例子，和你一样。因为第一次onsite还是决定不下来，又去了一次。第2
次见的人比较少。
【在 f****r 的大作中提到】
: 去google interview的同学们， 有人被要求过2nd onsite吗? 今天recruiter打电话说
: 上次（3weeks ago）的onsite不能move on, 要再给一次onsite (2-3people)。谁有经
: 验的给说说？ 谢谢了
|
l*****a
发帖数: 14598 | 3 我记得去年初似乎有好几个
似乎是头一天只面了算法数据结构
后来加面了design or large scalability
第2
【在 h*********3 的大作中提到】
: 我听说个一个例子，和你一样。因为第一次onsite还是决定不下来，又去了一次。第2
: 次见的人比较少。
|
f****r
发帖数: 30 | 4 第二次onsite更难吗？你听说的人有没有最后拿到offer?
第2
【在 h*********3 的大作中提到】
: 我听说个一个例子，和你一样。因为第一次onsite还是决定不下来，又去了一次。第2
: 次见的人比较少。
|
f****r
发帖数: 30 | 5 我的情况是， 第一次算法，coding, design， large scalability 全问了，
recruiter 说第二次onsite是 focus on 算法和coding。 是不是我第一次这方面
feedback不够好？
第一次onsite被问的问题好像特别多， 每个问题都不给多少时间。 所以最后虽然都做
出来了，但可能很多不是最优解。 不过interviewer也不给提示， 所以我也不知道最
后又没有最优解。
【在 l*****a 的大作中提到】
: 我记得去年初似乎有好几个
: 似乎是头一天只面了算法数据结构
: 后来加面了design or large scalability
:
: 第2
|
g*********s
发帖数: 1782 | 6 why not post ur problems? daniu here most likely would figure out the
optimal solutions.
【在 f****r 的大作中提到】
: 我的情况是， 第一次算法，coding, design， large scalability 全问了，
: recruiter 说第二次onsite是 focus on 算法和coding。 是不是我第一次这方面
: feedback不够好？
: 第一次onsite被问的问题好像特别多， 每个问题都不给多少时间。 所以最后虽然都做
: 出来了，但可能很多不是最优解。 不过interviewer也不给提示， 所以我也不知道最
: 后又没有最优解。
|
f****r
发帖数: 30 | 7 遇到的都是新题，还没来得及总结detail.
记得有道题是， stl vector, 问有什么办法avoid resize 时的 memory copy， 同时
要求keep constant time access.
【在 g*********s 的大作中提到】
: why not post ur problems? daniu here most likely would figure out the
: optimal solutions.
|
g*********s
发帖数: 1782 | 8 do u mean the trick of "push_back() to resize() and loop"?
【在 f****r 的大作中提到】
: 遇到的都是新题，还没来得及总结detail.
: 记得有道题是， stl vector, 问有什么办法avoid resize 时的 memory copy， 同时
: 要求keep constant time access.
|
f****r
发帖数: 30 | 9 don't get you.
The purpose is to reduce the cost of resize in a vector, which is a common
problem in dynamic array when you don't know the maximum size you need at
the beginning.
【在 g*********s 的大作中提到】
: do u mean the trick of "push_back() to resize() and loop"?
|
g*********s
发帖数: 1782 | 10 then what stl does now is most likely the optimal already: double the size
and copy when the current limit is reached.
i don't think u can "avoid copy" as you said originally. "reduce the cost"
makes more sense and i guess that's what the interviewer means.
common
at
【在 f****r 的大作中提到】
: don't get you.
: The purpose is to reduce the cost of resize in a vector, which is a common
: problem in dynamic array when you don't know the maximum size you need at
: the beginning.
|
|
|
t**v
发帖数: 101 | 11 I think this question is asking how stl vector's implementation can be
modified. How about using a pointer to point to the newly allocated
memory? I.e. X->X, instead of allocating 2X and copying from X.
【在 f****r 的大作中提到】
: 遇到的都是新题，还没来得及总结detail.
: 记得有道题是， stl vector, 问有什么办法avoid resize 时的 memory copy， 同时
: 要求keep constant time access.
|
g*********s
发帖数: 1782 | 12 then how u guarantee constant random access?
if there's a better scheme, stl would use it.
【在 t**v 的大作中提到】
: I think this question is asking how stl vector's implementation can be
: modified. How about using a pointer to point to the newly allocated
: memory? I.e. X->X, instead of allocating 2X and copying from X.
|
d******r
发帖数: 281 | |
y*********e
发帖数: 518 | 14 Let's say we don't use a single array for storage. Instead, we use a list of
arrays.
Let each storage array to be size of M, which is a constant.
To access the Kth element, we can know in which storage array and in which
position in that array the element is located.
Accessing array is constant. If we can indexing the storage arrays and find
which one it is located in a constant time, then everything could be done in
constant time.
That would be simple. Maintain an array that stores the pointer addresses of
all storage arrays. We call this array as the descriptor array.
So the solution works like this:
1. Create a descriptor array of size K
2. Create a storage array of size M (then we know our vector can store up to
K*M elements)
3. To create a new element -- check whether we need to grow:
3a. To grow, create a new storage array of size M, and store its pointer
address into the descriptor array
3b. Store the new element in the new storage array just now created.
4. To access an element by index, compute which storage array it is located.
Then we go to that storage array.
So access is done in constant time. Growth of vector does not require copying
existing elements.
【在 g*********s 的大作中提到】
: then how u guarantee constant random access?
: if there's a better scheme, stl would use it.
|
g*********s
发帖数: 1782 | 15 if the question is just "avoid copying in growth", w/ any other expense
allowed, yes this works.
but w/ this scheme, obviously any vector variable would need more bytes
because of the index array. also memory fragmentation is worse.
and how about erase()?
anyway, this might be an open-end question and the interviewer just
wants to hear ur thoughts and ideas.
list of
which
find
done in
addresses of
【在 y*********e 的大作中提到】
: Let's say we don't use a single array for storage. Instead, we use a list of
: arrays.
: Let each storage array to be size of M, which is a constant.
: To access the Kth element, we can know in which storage array and in which
: position in that array the element is located.
: Accessing array is constant. If we can indexing the storage arrays and find
: which one it is located in a constant time, then everything could be done in
: constant time.
: That would be simple. Maintain an array that stores the pointer addresses of
: all storage arrays. We call this array as the descriptor array.
|
f****r
发帖数: 30 | 16 This is the best answer so far, though you still assumes the maximum size of
the vector is K*M.
of
find
in
of
【在 y*********e 的大作中提到】
: Let's say we don't use a single array for storage. Instead, we use a list of
: arrays.
: Let each storage array to be size of M, which is a constant.
: To access the Kth element, we can know in which storage array and in which
: position in that array the element is located.
: Accessing array is constant. If we can indexing the storage arrays and find
: which one it is located in a constant time, then everything could be done in
: constant time.
: That would be simple. Maintain an array that stores the pointer addresses of
: all storage arrays. We call this array as the descriptor array.
|
g*********s
发帖数: 1782 | 17 as long as K*M == max_size of std::vector, it's fine.
the design of vector always carries trade-off given the semantics set. i
don't think there's one "optimal solution" in all aspects.
size of
【在 f****r 的大作中提到】
: This is the best answer so far, though you still assumes the maximum size of
: the vector is K*M.
:
: of
: find
: in
: of
|
y*********e
发帖数: 518 | 18 I just provided a direction of thought. The solution can be further improved
to provide erase function as well as avoiding memory fragmentation.
A simple enhancement is that storage array size could be dynamic. Well, I agree
with you that depending on the situation and requirement, this is an
open-ended question. The interviewer is concerned about the approach that
the candidate takes.
【在 g*********s 的大作中提到】
: if the question is just "avoid copying in growth", w/ any other expense
: allowed, yes this works.
: but w/ this scheme, obviously any vector variable would need more bytes
: because of the index array. also memory fragmentation is worse.
: and how about erase()?
: anyway, this might be an open-end question and the interviewer just
: wants to hear ur thoughts and ideas.
:
: list of
: which
|
h***n
发帖数: 276 | 19 I think this solution can avoid k*M upper limit if we allow the index array
to be enlarged as a dynamic array
also LZ, any other problem you can share? thx
of
find
in
of
【在 y*********e 的大作中提到】
: Let's say we don't use a single array for storage. Instead, we use a list of
: arrays.
: Let each storage array to be size of M, which is a constant.
: To access the Kth element, we can know in which storage array and in which
: position in that array the element is located.
: Accessing array is constant. If we can indexing the storage arrays and find
: which one it is located in a constant time, then everything could be done in
: constant time.
: That would be simple. Maintain an array that stores the pointer addresses of
: all storage arrays. We call this array as the descriptor array.
|
h**k
发帖数: 3368 | 20 正常，第一次的onsite的得分可能是edge case，可要可不要，或者第一次面试中评价
分不错，但是有面试官对你评价很低，
所以需要加试来决定。
【在 f****r 的大作中提到】
: 去google interview的同学们， 有人被要求过2nd onsite吗? 今天recruiter打电话说
: 上次（3weeks ago）的onsite不能move on, 要再给一次onsite (2-3people)。谁有经
: 验的给说说？ 谢谢了
|
