BB onsite 4轮

zzgzzm 发表于 2016-10-10 13:19
"4 billion 的数里面找missing number 这个大家有什么好想法吗"?
"Cracking the Coding Interview" 里就 ...

谢谢您~ 我去找一下~ 这本书我没咋看。。。

何打发123 发表于 2016-10-10 21:36
谢谢您~ 我去找一下~ 这本书我没咋看。。。

应该就是把所有的数加起来， 取个mod。。。 然后两个missing数字就是one pass加起来的sum取mod， 以及数字两两的乘积， 以此类推。。。 这样用这些值可以推出 根为missing number的polynomial， 解之就可以得到想要的数字。 这样应该是空间最小的方法。

powerdesk 发表于 2016-10-10 22:13
应该就是把所有的数加起来， 取个mod。。。 然后两个missing数字就是one pass加起来的sum取mod， 以及数 ...

一脸懵逼。。。这说的啥。。。

何打发123 发表于 2016-10-10 22:28
一脸懵逼。。。这说的啥。。。

假设 有 {1,2,3 ... 10} 十个数字 把数字k拿掉的话， 知道剩下九个数字的和， 再用十个数字的总和减去九个数字的和就是的少的数字k。

再假设 有 {1,2,3 ... 10} 十个数字 把数字k1和k2拿掉的话， 知道8个数字的和， 和八个数字的乘积， 就可以知道 k1+k2=-b/a 和 k1*k2=c/a, 然后解 a*x^2+b*x+c=0的方程就可以得到k1, k2.

当有多个数字missing的话， 仍然可以follow这个思路。

优化： 因为数字可能较多， 为了节省空间， 于是把 得到的和(sum of the 8 numbers, product of the 8 numbers) 除以 n 去余数。 这样就控制了储存数据的大小。

这样说， make sense么？

何打发123 发表于 2016-10-10 21:36
谢谢您~ 我去找一下~ 这本书我没咋看。。。

Problem 12.3 (Page 72)  (Cracking the Coding Interview, 4th Ed)

powerdesk 发表于 2016-10-10 22:13
应该就是把所有的数加起来， 取个mod。。。 然后两个missing数字就是one pass加起来的sum取mod， 以及数 ...

我记得不是说，如果加起来会有溢出么？ 边加边减，也可能在你上一个时候溢出。我忘了，用bitsit 还是 bit manu 什么，解决。至今没明白，怎么用。

cicean 发表于 2016-10-11 03:37
我记得不是说，如果加起来会有溢出么？ 边加边减，也可能在你上一个时候溢出。我忘了，用bitsit 还是 bit ...

溢出 就是取余数啊， 但是如果你主动去取余数的话你就会知道那个数字。。。 取余数就可以防止溢出

请问lz多久得到的回信啊

楼主，能详细讲一下那个两个人碰见概率的问题么？