算法
十道海量数据处理面试题与十个方法大总结 收藏
海量数据处理:十道面试题与十个海量数据处理方法总结
作者:July、youwang、yanxionglu。
时间:二零一一年三月二十六日
说明:本文分为俩部分,第一部分为10道海量数据处理的面试题,第二部分为10个海量数据处理的方法总结。有任何问题,欢迎交流、指正。
出处:doc.guandang.net。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据,提取出某日访问百度次数最多的那个IP。
此题,在我之前的一篇文章:算法里头有所提到,当时给出的方案是:IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存,然后进行统计。
再详细介绍下此方案:首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法,比如模1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。
2、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。
假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。),请你统计最热门的10个查询串,要求使用的内存不能超过1G。
典型的Top K算法,还是在这篇文章里头有所阐述,详情请参见:解析Hash表算法。
文中,给出的最终算法是:第一步、先对这批海量数据预处理,在O(N)的时间内用Hash表完成排序;然后,第二步、借助堆这个数据结构,找出Top K,时间复杂度为N‘logK。
即,借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比所以,我们最终的时间复杂度是:O(N) + N'*O(logK),(N为1000万,N’为300万)。ok,更多,详情,请参考原文。
或者:采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。
十道海量数据处理面试题与十个方法大总结_IT/计算机_专业资料。2011/5/9 十道海量数据处理面试题与十个方法…欢迎 in7deforever 我的: 空间 欢迎 in7deforever! ...
十道海量数据处理面试题与十个方法大总结_信息与通信_工程科技_专业资料。第一部分为10道海量数据处理的面试题,第二部分为10个海量数据处理的方法总结。海量...
此文, 却无任何收获, 那么, 我也甘愿背负这样的罪名, :-), 同时, 此文可以看做是对这篇文章: 十道海量数据处理面试题与十个方法大总结的一般抽象 性总结。 ...
前言本博客内曾经整理过有关海量数据处理的 10 道面试题 (十道海量数据处理面试题与十个 方法大总结),此次除了重复了之前的 10 道面试题之后,重新多整理了 7...
如果读者读罢此文,却无任何收获,那么,我也甘愿背负这样的罪名,:-),同时,此文可以看做是对 这篇文章:十道海量数据处理面试题与十个方法大总结的一般抽象性总结。...
此文, 却无任何收获, 那么, 我也甘愿背负这样的罪名, :-), 同时, 此文可以看做是对这篇文章: 十道海量数据处理面试题与十个方法大总结的一般抽象 性总结。 ...
教你如何迅速秒杀99%的海量数据处理面试题_IT/计算机_专业资料。十道海量数据处理面试题与十个方法大总结的一般抽象性总结教你如何迅速秒杀99%的海量数据处理面试题...
前言本博客内曾经整理过有关海量数据处理的 10 道面试题(十道海量数据处理面试题与十个方法大总结), 此次除了重复了之前的 10 道面试题之后,重新多整理了 7 ...
”-- 十道海量数据处理面试题与十个方法大总结。 注:Hash 取模是一种等价映射,不会存在同一个元素分散到不同小文件中 去的情况,即这里采用的是 mod1000 ...
如果读者读罢此文, 却无任何收获, 那么, 我也甘愿背负这样的罪名, :-), 同时, 此文可以看做是对这篇文章: 十道海量数据处理面试题与十个方法大总结的一般抽象...
,如果读者读罢此文,却无任何收获,那么,我也甘愿背负这样的罪名,:-),同时,此文可以看做是对这篇文章:十道海量数据处理面试题与十个方法大总结的一般抽象性总结。...
”--十道海量数据处理面试题与十个方法大总结。 关于本题,还有几个问题,如下: 1、Hash 取模是一种等价映射,不会存在同一个元素分散到不同小文件中去的情况,...
热门文档