Category Archives: Large scale data

如何秒杀99%的海量数据处理面试题(转载)

海量数据处理:十道面试题与十个海量数据处理方法总结 作者:July、youwang、yanxionglu。 时间:二零一一年三月二十六日 说明:本文分为俩部分,第一部分为10道海量数据处理的面试题,第二部分为10个海量 数据处理的方法总结。 本文之总结:教你如何迅速秒杀掉:99%的海量数据处理面试题。有任何问题,欢迎随 时交流、指正。 出处:http://blog.csdn.net/v_JULY_v。 —————————————— 第一部分、十道海量数据处理面试题 1、海量日志数据,提取出某日访问百度次数最多的那个IP。 首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中 。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法,比如模1000,把 整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash _map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最 大的IP中,找出那个频率最大的IP,即为所求。 或者如下阐述(雪域之鹰): 算法思想:分而治之+Hash 1.IP地址最多有2^32=4G种取值情况,所以不能完全加载到内存中处理; 2.可以考虑采用“分而治之”的思想,按照IP地址的Hash(IP)%1024值,把海量IP日志 分别存储到1024个小文件中。这样,每个小文件最多包含4MB个IP地址; 3.对于每一个小文件,可以构建一个IP为key,出现次数为value的Hash map,同时记录 当前出现次数最多的那个IP地址; 4.可以得到1024个小文件中的出现次数最多的IP,再依据常规的排序算法得到总体上出 现次数最多的IP; 2、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询 串的长度为1-255字节。 假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如 果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多, 也就是越热门。),请你统计最热门的10个查询串,要求使用的内存不能超过1G。 典型的Top K算法,还是在这篇文章里头有所阐述,详情请参见:十一、从头到尾 彻底解析Hash表算法。 文中,给出的最终算法是: 第一步、先对这批海量数据预处理,在O(N)的时间内用Hash表完成统计(之前写 成了排序,特此订正。July、2011.04.27); 第二步、借助堆这个数据结构,找出Top K,时间复杂度为N‘logK。 即,借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护 … Continue reading

Posted in Large scale data | Leave a comment