Google面试题

[northernwolf]

2. 假设一个无穷无尽的流，里面都是整数，每次里面随机每10个每10个取样。每次取到的样本当然都不一样。

I think this means that:

let A = { a1, a2, a3, .....}
ai != ak if (i!=k)

ak -> infinite if k -> infinite


要求只保留10个数字作为数组，而且这10个在整个流的出现概率和在这个数组里面出现的概率是一样的。

it seems imposible we have 这10个数字作为数组, because 这10个在整个流的出现概率 is 0 and 这10个数字这在个数组里面出现的概率 is 100%.

Am I wrong?

虽然整数的范围是无限的，但在计算机里是有限的。对于１６位机器来讲，是－３２７６８到＋３２７６７。因此每一个样本的概率是１／６５５３６。

 

[northernwolf]

对不起我错了，我忘记第二个数组没排序了。

 

[todd_zhang]

感觉应该有O(n)答案.

 

[mooncake]

1. 两个等长数组，如何判断里面的元素是不是完全一样，只是次序不对而已。要求省时间也省空间。

2. 假设一个无穷无尽的流，里面都是整数，每次里面随机每10个每10个取样。每次取到的样本当然都不一样。要求只保留10个数字作为数组，而且这10个在整个流的出现概率和在这个数组里面出现的概率是一样的。


哪位大侠有好的解决方案?

1.先求各元素hash值并求和，比较两个和，不相等则结束。相等按先排序一个数组，然后比较，如果hash算法好，时间是0(n)，空间是0(1)
第二题看不懂

 

[blueray]

True. That's why I like his one.

2nlog(n) + n

如果sort数组1再binary search数组2， 结果是2nlog(n), 少n次比较。

 

[WebExplorer]

This is wrong! See the following counter example(assuming you sort the first array):
array 1: 1 2 3
array 2: 2 2 2

How about using the following approach?
sort one arrays in merge : running time n log(n).
do binary search for all member of the other arrays based on the sorted array.
No extra memory is needed.

 

[xjl]

This is wrong! See the following counter example(assuming you sort the first array):
array 1: 1 2 3
array 2: 2 2 2

Yes. I am wrong. thanks

 

[Attitude]

deviation sum含有乘法运算，乘法不是一个O(1)运算。

for the 1stq
do the mean for each group, if the mean is the same, it is possible.
do the deviation sum for each group, if it is the same again. it is .
That is maybe the quickest and least space will be used.

Great question.

 

[newer]

After 2 is found in array 1, change 2 to NaN or a value above
max value in array 1 if array 1 is not needed anymore.

This is wrong! See the following counter example(assuming you sort the first array):
array 1: 1 2 3
array 2: 2 2 2

 

[陨石]

美国人也没什么好办法：
http://www.mitbbs.com/article_t1/JobHunting/31534995_0_1.html