6+电池问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Apple - 家有苹果

6+电池问题

6+电池问题# Apple - 家有苹果

q*n2014-11-13 08:11

1 楼

闲来无事，拽着正在玩lego的儿子扯话题，问他：
“觉得妈妈做饭好吃吗？”
“好吃啊！”
“最喜欢吃什么哩？”
“蛋炒饭！”
@#￥%……&×（）——）（×&……%￥#@#￥%……&×（
老天，原来我如此用心的做饭，您竟然只钟爱蛋炒饭！！！！！
好吧～
换个花样，空心菜炒饭，您愿爱就爱，不爱也得吃！！！
玉米粒，青豆用热水煮过，豆芽也飞一下水，空水，备用。
热锅，炒香蒜蓉，盐，白胡椒调味，加入白蘑菇，空心菜炒软，再放先前煮过的菜，米
饭，炒匀就好。
加碟小菜：虎虾炒蛋～

f*r2014-11-13 08:11

2 楼

去google interview的同学们，有人被要求过2nd onsite吗? 今天recruiter打电话说
上次（3weeks ago）的onsite不能move on, 要再给一次onsite (2-3people)。谁有经
验的给说说？谢谢了

n*u2014-11-13 08:11

3 楼

用电脑usb充到从60%冲到80%，大概一个半小时，然后插座充一夜，到90%,拔下插头在
插上，15min到94%，重启后显示100%。
是不是calibration有问题。

h*32014-11-13 08:11

4 楼

我听说个一个例子，和你一样。因为第一次onsite还是决定不下来，又去了一次。第2
次见的人比较少。

【在 f****r 的大作中提到】

: 去google interview的同学们，有人被要求过2nd onsite吗? 今天recruiter打电话说
: 上次（3weeks ago）的onsite不能move on, 要再给一次onsite (2-3people)。谁有经
: 验的给说说？谢谢了

h*z2014-11-13 08:11

5 楼

前97%很快就冲完了，最后的3% takes forever

l*a2014-11-13 08:11

6 楼

我记得去年初似乎有好几个
似乎是头一天只面了算法数据结构
后来加面了design or large scalability

第2

【在 h*********3 的大作中提到】

: 我听说个一个例子，和你一样。因为第一次onsite还是决定不下来，又去了一次。第2
: 次见的人比较少。

f*r2014-11-13 08:11

7 楼

第二次onsite更难吗？你听说的人有没有最后拿到offer?

第2

【在 h*********3 的大作中提到】

: 我听说个一个例子，和你一样。因为第一次onsite还是决定不下来，又去了一次。第2
: 次见的人比较少。

f*r2014-11-13 08:11

8 楼

我的情况是，第一次算法，coding, design， large scalability 全问了，
recruiter 说第二次onsite是 focus on 算法和coding。是不是我第一次这方面
feedback不够好？
第一次onsite被问的问题好像特别多，每个问题都不给多少时间。所以最后虽然都做
出来了，但可能很多不是最优解。不过interviewer也不给提示，所以我也不知道最
后又没有最优解。

【在 l*****a 的大作中提到】

: 我记得去年初似乎有好几个
: 似乎是头一天只面了算法数据结构
: 后来加面了design or large scalability
:
: 第2

g*s2014-11-13 08:11

9 楼

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*r2014-11-13 08:11

10 楼

遇到的都是新题，还没来得及总结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*s2014-11-13 08:11

11 楼

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*r2014-11-13 08:11

12 楼

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*s2014-11-13 08:11

13 楼

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*v2014-11-13 08:11

14 楼

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*s2014-11-13 08:11

15 楼

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*r2014-11-13 08:11

16 楼

NIU REN.......

y*e2014-11-13 08:11

17 楼

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*s2014-11-13 08:11

18 楼

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*r2014-11-13 08:11

19 楼

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 的大作中提到】

g*s2014-11-13 08:11

20 楼

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*e2014-11-13 08:11

21 楼

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*n2014-11-13 08:11

22 楼

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 的大作中提到】