Google面试题

[陨石]

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

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


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

 

[坐在墙上等红杏]

问问陈景润吧

 

[C est La Vie]

2. as long as there is all integers appear the same number of time and in the same sequence?

hey, what do I know...just wild guess

 

[苦逼热狗]

1. 两数组里头的元素结构未知吧？能得到单个element的hash的话，既然长度一样
就从array 1按顺序取出1个element，然后带入array 2，进行比较和抵消。
虽然运行速度是O(N*N)不过至少比排序以后一一比较快吧

 

[blueray]

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

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

sort two arrays with merge sort: running time n log(n)
compare all elements one by one in two arrays: running time n

Total running time is n log(n)

No extra memory is needed.

 

[xjl]

sort two arrays with merge sort: running time n log(n)
compare all elements one by one in two arrays: running time n

Total running time is n log(n)

No extra memory is needed.

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]

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?

 

[todd_zhang]

先把两个数组转成INT数组, 求和. 比较SUM是不是一样．
这样最快．

 

[苦逼热狗]

我觉得，单纯的相加求和不行，因为1+2和3+0的summation是一样的

 

[wuxl650116]

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.

 

[wuxl650116]

for the second I would try
get the first from first sample, get the second from the second sample, so do the rest.

It maybe the answer.

 

[blueray]

Nice. Yours is better and more efficient. The search stops earlier if two arrays are different.

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.

 

[westaa]

sort two arrays with merge sort: running time n log(n)
compare all elements one by one in two arrays: running time n

Total running time is n log(n)

No extra memory is needed.

2nlog(n) + n

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

 

[northernwolf]

2nlog(n) + n

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

排队第一个数组，nlog(n)
一对一数组元素比较，　最多n
因此　total <= nlog(n) + n

 

[westaa]

一对一数组元素比较，　最多n