谷歌面试题一枚

机械开发代码久了，看了看一些面试题，可以活跃大脑，最近网上看了一题面试题。

 

 

 

Google面试题：找几百亿数据的中值

有几百亿的整数，分布的存储到几百台通过网络连接的计算机上，你能否开发出一个算法和系统，找出这几百亿数据的中值？就是在一组排序好的数据中居于中间的数。显然，一台机器是装不下所有的数据，也尽量少用网络带宽。

我的算法训练挺少的，只能自己谈些自己的心得。

1.获得题目，要仔细研读，迅速转化为数学模型。

混乱 -->有序 ， 局部-->整体。

大问题化解为小问题来求解。

这时，我们的思路 大概就是出来了：如果每一台机器上的数据都是无序的，我们需要排序，排好序了从这些局部中

综合到整体， 然后获得一个正确答案。

2. 举例归纳。确立问题的边界。

1    4    5    6   15   44    55

3     7  11   12  13  18   35   

总的顺序为 1  3  4   5   6  7  11  12  13   15  18  35  44 55.

总共 14个数，中值为 11 12 。

直白的想法，这是归并排序吗，带宽不允许。

当然，如果题目变成了，求任意个位置的数值，那么归并排序就是一个完全的解空间。

现在题目很特殊，就是一个中值，我们要充分利用这个内涵。

3. 发掘约束，削减解空间。

观察样本，利用直觉，第一排中间是6，第二是12，小于6的全部抛弃， 大于12的全部抛弃。

中值在 6   15   44    55，  3     7  11   12中寻找，可以吗？

答案好像是可以的，假设中值在问号位置，

  *  ？ *    6   15   44    55

3     7  11   12  13  18   35  

那么 ？ < 6 <12, 那么 ？ 排在整个序列中，那么它后面还有 4+4> (14/2)了，所以它的位置肯定不为中间，那么同样道理，中值也不肯出现在 下一排的 比较大的那部分，

反证法证完毕。

我们可以通过传送一个值，一下排除一半的数据，同样道理，我们继续总剩下的序列中，通过这个方式，

递归地排除好多数据，最后夹逼到中值，有点类似求极限，呵呵。

当然，这里有些小细节没有给出，如果几排中值相等如何处理等等，如果递归，我想这些聪明的读者已经想到，先到这里吧， 作为一个民工，我他妈的还要继续给老板创造价值，先把那80%不需要头脑的活干完再说。