面试题目-大数据量海量数据处理

《面试题目-大数据量海量数据处理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、发信人:phylips(星星

2、

3、一年磨十剑),信区:Algorithm标题:面试题目-大数据量专题发信站:兵马俑BBS(ThuNov2616:30:442009),本站(bbs.xjtu.edu.cn)1.给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。2.有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序3.有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词4.海量日志数据，提

4、取出某日访问百度次数最多的那个IP。5.2.5亿个整数中找出不重复的整数，内存空间不足以容纳这2.5亿个整数。6.海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。7.怎么在海量数据中找出重复次数最多的一个8.上千万or亿数据（有重复），统计其中出现次数最多的前N个数据。统计可以用hash,二叉数,trie树。对统计结果用堆求出现的前n大数据。增加点限制可以提高效率，比如出现次数>数据总数／N的一定是在前N个之内9.1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？10.一个文本文件，大约有一万行，每行一个词，要

5、求统计出其中最频繁出现的前十个词。请给出思想，给时间复杂度分析。11.一个文本文件，也是找出前十个最经常出现的词，但这次文件比较长，说是上亿行或者十亿行，总之无法一次读入内存，问最优解。12.有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复要按照query的频度排序13.100w个数中找最大的前100个数14.寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复

6、度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。（1）请描述你解决这个问题的思路；（2）请给出主要的处理流程，算法，以及算法的复杂度。15.一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)？本文由phylips@bmy收集整理，转载请注明出处http://bbs.xjtu.edu.cn谢谢合作。--如果可以愿把这生命燃烧只留下星星的传说悲伤而让人怀念==※来源:．兵马俑BBShttp://bbs.xjtu.edu.cn[FROM:219.224.191.247]发信人:

7、phylips(星星

8、

9、一年磨十剑),信区:Algorithm标题:大数据量，海量数据处理方法总结发信站:兵马俑BBS(ThuNov2616:32:382009),本站(bbs.xjtu.edu.cn)最近有点忙，稍微空闲下来，发篇总结贴。大数据量的问题是很多面试笔试中经常出现的问题，比如baidugoogle腾讯这样的一些涉及到海量数据的公司经常会问到。下面的方法是我对海量数据的处理方法进行了一个一般性的总结，当然这些方法可能并不能完全覆盖所有的问题，但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目，方法不一定最优，如果你有更好的处理方法

10、，欢迎与我讨论。1.Bloomfilter适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集基本原理及要点：对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是countingBloomfilter，用一个counter数组代替位数组，就可以支持删除了。还有一个比较重要的问题，如何根据输入元素个数n，确定位数组m的大小及hash函数个数。当ha

11、sh函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1/E)*lge大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。注意这里m与n的单位不同，m是bit为单位，而n则是以