机械开发代码久了,看了看一些面试题,可以活跃大脑,最近网上看了一题面试题。
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%不需要头脑的活干完再说。
|
分享到:
相关推荐
c++面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试...
google面试题google面试题
面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题面试题...
【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】分布式相关面试题大全面试题【BAT必备】...
JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题
2023java最新阿里巴巴面试题2023java最新阿里巴巴面试题2023java最新阿里巴巴面试题2023java最新阿里巴巴面试题2023java最新阿里巴巴面试题2023java最新阿里巴巴面试题2023java最新阿里巴巴面试题2023java最新阿里...
JavaOOP面试题 Java集合/泛型面试题 Java异常面试题 Java中的IO与NIO面试题 Java反射面试题 Java序列化面试题 Java注解面试题 多线程&并发面试题 JVM面试题 Mysql面试题 Redis面试题 Memcached面试题 MongoDB面试题 ...
每年招聘的时候,做笔试难免会遇到一些经典的面试题,而好多是google已经出过的
c#笔试面试题 c#笔试面试题 c#笔试面试题 c#笔试面试题 c#笔试面试题
以后会慢慢把Java相关的面试题、计算机网络等都加进来,其实这不仅仅是一份面试题,更是一份面试参考,让你熟悉面试题各种提问情况,当然,项目部分,就只能看自己了,毕竟每个人简历、实习、项目等都不一样。面试题...
最全的j2EE面试题,题量大、经典,是我面试的整理试题 1、java笔试题大集合 2、各个公司面试题 3、J2EE初学者面试题 4、J2EE面试题(打码查错题) 5、java_华为笔试题 6、java常见面试题 7、java程序员面试宝典 8、...
11谷歌面试题精讲
Google21道面试题 Google公司的面试 google面试题2 GOOGLE面试题--答案
JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题JAVA面试题
.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题
ERP工程师面试题ERP工程师面试题ERP工程师面试题ERP工程师面试题
程序员面试题精选 C++ 算法 微软 google 程序员面试题精选 C++ 算法 微软 google
java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题java面试题...
.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题.net面试题
google的面试题,很有挑战性...........