贡献两道google面试题 - 未名空间MITBBS历史存档

h*82011-02-22 08:02

1 楼

1。 Suppose we have a stream of web clicks. Now you need to provide at any
time the count of web clicks during the past 1 minute. To be specific, you
get informed whenever a web click happens. You need to provide a function "
getCount()" such that once called, return the count of clicks during the
past 1 minute. The solution will be both constant in time and space.
2。 N * N MATRIX, 只有一行完全是 0, 其他行有 0 也有 1, 怎么最快找到完全是 0
的那一行. 平均O()和 WORST CASE O() 是多少?

g*s2011-02-22 08:02

2 楼

看着都不像真题啊。careercup?

any
you
function "
0

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

: 1。 Suppose we have a stream of web clicks. Now you need to provide at any
: time the count of web clicks during the past 1 minute. To be specific, you
: get informed whenever a web click happens. You need to provide a function "
: getCount()" such that once called, return the count of clicks during the
: past 1 minute. The solution will be both constant in time and space.
: 2。 N * N MATRIX, 只有一行完全是 0, 其他行有 0 也有 1, 怎么最快找到完全是 0
: 的那一行. 平均O()和 WORST CASE O() 是多少?

f*g2011-02-22 08:02

3 楼

1. Circular Array来记录
2. 提示了平均，和Worst Case，说明这两个不一样。
用一个queue来保存行号。
每次循环scan一列。
每次循环中，提出一个行号，如果当前为0，压回队列
如果为1，舍弃。
最后queue只剩一个元素
Worst case，O(n^2)
平均，每次舍弃一半的行。总共O(n)

l*a2011-02-22 08:02

4 楼

how do u handle the size of array

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

: 1. Circular Array来记录
: 2. 提示了平均，和Worst Case，说明这两个不一样。
: 用一个queue来保存行号。
: 每次循环scan一列。
: 每次循环中，提出一个行号，如果当前为0，压回队列
: 如果为1，舍弃。
: 最后queue只剩一个元素
: Worst case，O(n^2)
: 平均，每次舍弃一半的行。总共O(n)

f*g2011-02-22 08:02

5 楼

我的理解:
时间总要有个单位吧
如果要是以每秒计算，记录，就是60个吧。

l*a2011-02-22 08:02

6 楼

题目的要求是可能有无数的click，前后时间跨度很大
对任意的click都可以返回1分钟之内的点击数目
你打算建多少个数组？

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

: 我的理解:
: 时间总要有个单位吧
: 如果要是以每秒计算，记录，就是60个吧。

P*a2011-02-22 08:02

7 楼

60就够了，不我想的是队列
每秒收到的计数到temp, 下一秒开始前清空并push到queue并dequeue

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

: 题目的要求是可能有无数的click，前后时间跨度很大
: 对任意的click都可以返回1分钟之内的点击数目
: 你打算建多少个数组？

f*g2011-02-22 08:02

8 楼

恩
再维护一个total
每秒更新。
query就是O(1)

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

: 60就够了，不我想的是队列
: 每秒收到的计数到temp, 下一秒开始前清空并push到queue并dequeue

h*82011-02-22 08:02

9 楼

what is your resolution here? you push all the clicks within 1 second to
queue? Say you have 100 clicks in a second, how many items do you push to
queue?
If you push 100 items, how to get constant space?
If you enqueue 1 item, how to differetiate those 100 clicks?

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

: 60就够了，不我想的是队列
: 每秒收到的计数到temp, 下一秒开始前清空并push到queue并dequeue

P*a2011-02-22 08:02

10 楼

100下存在temp里啊，每秒清、压一次temp

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

: what is your resolution here? you push all the clicks within 1 second to
: queue? Say you have 100 clicks in a second, how many items do you push to
: queue?
: If you push 100 items, how to get constant space?
: If you enqueue 1 item, how to differetiate those 100 clicks?

P*a2011-02-22 08:02

11 楼

哦，对，只能精确到秒级的，要想增大精确度就得增大queue里的element了

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

: what is your resolution here? you push all the clicks within 1 second to
: queue? Say you have 100 clicks in a second, how many items do you push to
: queue?
: If you push 100 items, how to get constant space?
: If you enqueue 1 item, how to differetiate those 100 clicks?

f*42011-02-22 08:02

12 楼

我觉得这个精确到秒级就可以了吧

m*k2011-02-22 08:02

13 楼

第二题, 每次舍弃一半的行, 怎么得到O(n)的?

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

: 1. Circular Array来记录
: 2. 提示了平均，和Worst Case，说明这两个不一样。
: 用一个queue来保存行号。
: 每次循环scan一列。
: 每次循环中，提出一个行号，如果当前为0，压回队列
: 如果为1，舍弃。
: 最后queue只剩一个元素
: Worst case，O(n^2)
: 平均，每次舍弃一半的行。总共O(n)

z*c2011-02-22 08:02

14 楼

(N + N/2 + N/4 + ... + 1) < 2N
O(N)

【在 m**k 的大作中提到】

: 第二题, 每次舍弃一半的行, 怎么得到O(n)的?

z*c2011-02-22 08:02

15 楼

http://en.wikipedia.org/wiki/Circular_buffer

you
0

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

: 1。 Suppose we have a stream of web clicks. Now you need to provide at any
: time the count of web clicks during the past 1 minute. To be specific, you
: get informed whenever a web click happens. You need to provide a function "
: getCount()" such that once called, return the count of clicks during the
: past 1 minute. The solution will be both constant in time and space.
: 2。 N * N MATRIX, 只有一行完全是 0, 其他行有 0 也有 1, 怎么最快找到完全是 0
: 的那一行. 平均O()和 WORST CASE O() 是多少?

u*e2011-02-22 08:02

16 楼

1是真题
我onsite也遇到了

you
0

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

: 1。 Suppose we have a stream of web clicks. Now you need to provide at any
: time the count of web clicks during the past 1 minute. To be specific, you
: get informed whenever a web click happens. You need to provide a function "
: getCount()" such that once called, return the count of clicks during the
: past 1 minute. The solution will be both constant in time and space.
: 2。 N * N MATRIX, 只有一行完全是 0, 其他行有 0 也有 1, 怎么最快找到完全是 0
: 的那一行. 平均O()和 WORST CASE O() 是多少?

c*t2011-02-22 08:02

17 楼

看不懂第二题的solution
能不能麻烦说的更详细一些？

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

: 1. Circular Array来记录
: 2. 提示了平均，和Worst Case，说明这两个不一样。
: 用一个queue来保存行号。
: 每次循环scan一列。
: 每次循环中，提出一个行号，如果当前为0，压回队列
: 如果为1，舍弃。
: 最后queue只剩一个元素
: Worst case，O(n^2)
: 平均，每次舍弃一半的行。总共O(n)

h*82011-02-22 08:02

18 楼

I think the interviewer wants a solution that can handle cases of unlimited
precision here ...

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

: 哦，对，只能精确到秒级的，要想增大精确度就得增大queue里的element了

h*82011-02-22 08:02

19 楼

my solution:
Since you need to return the counts of clicks in the past minute at any time
, the idea of resetting the counter every minute won’t work here.
It is easy to see that this is an event-driven model. Basically we have two
kinds of events here. Once a web click happens at time t, we need to
increment the counter. At time t+1, the event expires, and we need to
decrement the counter. The value of the counter is a stair-case function,
with discontinuous being the events.
Basically we need to maintain a static counter (singleton?), which can be
read (say, by another thread) any time. We modify the counter whenever an
event happens.
Normally we can use priority queue keyed by time stamps to store events.
Actually we certainly can use that here, and when a click happens, insert
two events (increment event t and decrement event t+1) to the heap.
However, we can do better here since we know that one event only lead to one
more event. In fact, two queues will do. One is the queue of increment
events, and the other is that of decrement events. At any time we look at
the head of two queues, and take action accordingly. The time complexity is
now O(1), rather than O(log n) of the heap solution.
Even better, we know that whenever a web click happens, an event will be
generated and sent to you. So you do not need to keep any information there.
That is, whenever get informed at t, increment the counter and insert t+1
in another event queue, which will trigger decrement of the counter. But
still, the storage of old events is not constant. However, this problem can
be solved if we are allowed to send an event. That is, upon receiving
increment event at time t, we schedule to send a decrement event at time t+1
. We increase counter upon increment events and decrease it upon decrement
events. This way we do not need linear storage.

unlimited

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

: I think the interviewer wants a solution that can handle cases of unlimited
: precision here ...

h*82011-02-22 08:02

20 楼

1。 Suppose we have a stream of web clicks. Now you need to provide at any
time the count of web clicks during the past 1 minute. To be specific, you
get informed whenever a web click happens. You need to provide a function "
getCount()" such that once called, return the count of clicks during the
past 1 minute. The solution will be both constant in time and space.
2。 N * N MATRIX, 只有一行完全是 0, 其他行有 0 也有 1, 怎么最快找到完全是 0
的那一行. 平均O()和 WORST CASE O() 是多少?

g*s2011-02-22 08:02

21 楼

看着都不像真题啊。careercup?

any
you
function "
0

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

: 1。 Suppose we have a stream of web clicks. Now you need to provide at any
: time the count of web clicks during the past 1 minute. To be specific, you
: get informed whenever a web click happens. You need to provide a function "
: getCount()" such that once called, return the count of clicks during the
: past 1 minute. The solution will be both constant in time and space.
: 2。 N * N MATRIX, 只有一行完全是 0, 其他行有 0 也有 1, 怎么最快找到完全是 0
: 的那一行. 平均O()和 WORST CASE O() 是多少?

f*g2011-02-22 08:02

22 楼

1. Circular Array来记录
2. 提示了平均，和Worst Case，说明这两个不一样。
用一个queue来保存行号。
每次循环scan一列。
每次循环中，提出一个行号，如果当前为0，压回队列
如果为1，舍弃。
最后queue只剩一个元素
Worst case，O(n^2)
平均，每次舍弃一半的行。总共O(n)

l*a2011-02-22 08:02

23 楼

how do u handle the size of array

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

: 1. Circular Array来记录
: 2. 提示了平均，和Worst Case，说明这两个不一样。
: 用一个queue来保存行号。
: 每次循环scan一列。
: 每次循环中，提出一个行号，如果当前为0，压回队列
: 如果为1，舍弃。
: 最后queue只剩一个元素
: Worst case，O(n^2)
: 平均，每次舍弃一半的行。总共O(n)

f*g2011-02-22 08:02

24 楼

我的理解:
时间总要有个单位吧
如果要是以每秒计算，记录，就是60个吧。

l*a2011-02-22 08:02

25 楼

题目的要求是可能有无数的click，前后时间跨度很大
对任意的click都可以返回1分钟之内的点击数目
你打算建多少个数组？

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

: 我的理解:
: 时间总要有个单位吧
: 如果要是以每秒计算，记录，就是60个吧。

P*a2011-02-22 08:02

26 楼

60就够了，不我想的是队列
每秒收到的计数到temp, 下一秒开始前清空并push到queue并dequeue

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

: 题目的要求是可能有无数的click，前后时间跨度很大
: 对任意的click都可以返回1分钟之内的点击数目
: 你打算建多少个数组？

f*g2011-02-22 08:02

27 楼

恩
再维护一个total
每秒更新。
query就是O(1)

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

: 60就够了，不我想的是队列
: 每秒收到的计数到temp, 下一秒开始前清空并push到queue并dequeue

h*82011-02-22 08:02

28 楼

what is your resolution here? you push all the clicks within 1 second to
queue? Say you have 100 clicks in a second, how many items do you push to
queue?
If you push 100 items, how to get constant space?
If you enqueue 1 item, how to differetiate those 100 clicks?

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

: 60就够了，不我想的是队列
: 每秒收到的计数到temp, 下一秒开始前清空并push到queue并dequeue

P*a2011-02-22 08:02

29 楼

100下存在temp里啊，每秒清、压一次temp

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

: what is your resolution here? you push all the clicks within 1 second to
: queue? Say you have 100 clicks in a second, how many items do you push to
: queue?
: If you push 100 items, how to get constant space?
: If you enqueue 1 item, how to differetiate those 100 clicks?

P*a2011-02-22 08:02

30 楼

哦，对，只能精确到秒级的，要想增大精确度就得增大queue里的element了

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

: what is your resolution here? you push all the clicks within 1 second to
: queue? Say you have 100 clicks in a second, how many items do you push to
: queue?
: If you push 100 items, how to get constant space?
: If you enqueue 1 item, how to differetiate those 100 clicks?

f*42011-02-22 08:02

31 楼

我觉得这个精确到秒级就可以了吧

m*k2011-02-22 08:02

32 楼

第二题, 每次舍弃一半的行, 怎么得到O(n)的?

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

: 1. Circular Array来记录
: 2. 提示了平均，和Worst Case，说明这两个不一样。
: 用一个queue来保存行号。
: 每次循环scan一列。
: 每次循环中，提出一个行号，如果当前为0，压回队列
: 如果为1，舍弃。
: 最后queue只剩一个元素
: Worst case，O(n^2)
: 平均，每次舍弃一半的行。总共O(n)

z*c2011-02-22 08:02

33 楼

(N + N/2 + N/4 + ... + 1) < 2N
O(N)

【在 m**k 的大作中提到】

: 第二题, 每次舍弃一半的行, 怎么得到O(n)的?

z*c2011-02-22 08:02

34 楼

http://en.wikipedia.org/wiki/Circular_buffer

you
0

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

: 1。 Suppose we have a stream of web clicks. Now you need to provide at any
: time the count of web clicks during the past 1 minute. To be specific, you
: get informed whenever a web click happens. You need to provide a function "
: getCount()" such that once called, return the count of clicks during the
: past 1 minute. The solution will be both constant in time and space.
: 2。 N * N MATRIX, 只有一行完全是 0, 其他行有 0 也有 1, 怎么最快找到完全是 0
: 的那一行. 平均O()和 WORST CASE O() 是多少?

u*e2011-02-22 08:02

35 楼

1是真题
我onsite也遇到了

you
0

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

: 1。 Suppose we have a stream of web clicks. Now you need to provide at any
: time the count of web clicks during the past 1 minute. To be specific, you
: get informed whenever a web click happens. You need to provide a function "
: getCount()" such that once called, return the count of clicks during the
: past 1 minute. The solution will be both constant in time and space.
: 2。 N * N MATRIX, 只有一行完全是 0, 其他行有 0 也有 1, 怎么最快找到完全是 0
: 的那一行. 平均O()和 WORST CASE O() 是多少?

c*t2011-02-22 08:02

36 楼

看不懂第二题的solution
能不能麻烦说的更详细一些？

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

: 1. Circular Array来记录
: 2. 提示了平均，和Worst Case，说明这两个不一样。
: 用一个queue来保存行号。
: 每次循环scan一列。
: 每次循环中，提出一个行号，如果当前为0，压回队列
: 如果为1，舍弃。
: 最后queue只剩一个元素
: Worst case，O(n^2)
: 平均，每次舍弃一半的行。总共O(n)

y*g2011-02-22 08:02

37 楼

不解，你的解法要求每个click都设置一个timer? 1分钟如果有1百万个click就要维护1
百万个timer？

time
two

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

: my solution:
: Since you need to return the counts of clicks in the past minute at any time
: , the idea of resetting the counter every minute won’t work here.
: It is easy to see that this is an event-driven model. Basically we have two
: kinds of events here. Once a web click happens at time t, we need to
: increment the counter. At time t+1, the event expires, and we need to
: decrement the counter. The value of the counter is a stair-case function,
: with discontinuous being the events.
: Basically we need to maintain a static counter (singleton?), which can be
: read (say, by another thread) any time. We modify the counter whenever an

u*q2011-02-22 08:02

38 楼

If the required precision is not high (I don't think infinite precision has
any practical meaning and usage), we can keep a timer fired each second to
setup the decrease timer. Maintain a temp value, each click event add 1 to
temp (and total count). When the per second timer fires, if temp is 0, do
nothing. Otherwise copy temp to decrease timer (by parameter or another
storage variable) and clear temp to 0. So max 60 decrease timers are needed.

r*g2011-02-22 08:02

39 楼

第一题，感觉不大可能constant space and time。你要维护任意一分钟的信息，那么必然每次click
都得维护，这样才能把先前的click去掉，比如，把每次click的时间放在一个queue里面，每来一个新的
click决定是否去掉最早的click。
但是每一分钟维护的click的次数不一样，决定了你维护的queue大小不一样。