大量数据处理

1. 给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。  

2. 有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序 

 

3. 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词 

 

大家讨论讨论这三道题的算法 

分布式的MapReduce适合干这个事儿 

有效的应用外部排序我觉得就可以干这样的事情。。。 

要我的话 我会选择外部排序一个文件 +分层索引 

1. 外部排序，求交。 

2. 外部排序，归并。 

 

对于第一个题，网上有的解法是按照hash分段，通过对url求hash值，按照hash值进行分段，每一段存放一个文件，分段要求尽量将子文件的大小不超过内存要求，如果一个段太大，我们利用再hash，对子文件在进行hash分段。如果最好一个段还是很大，就使用外排。这样，两个大文件就都分段成了可以放在内存里的小文件，由于相同的url一定在一个段中，所以要查找相同的url只需要在相同的段中进行查找。 

经典的早期百度面试题。 

分块内部快速排序+多路归并 

====================================================

1给你a、b两个文件，各存放50亿条url，每条url各占用64字节，内存限制是4G，让你找出a、b文件共同的url。、 

2给你一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给你一个字典，用户输入一个单词，让你根据字典找出这个单词有多少个兄弟单词。  （这道题面试官说有O(1) 的解法，。。。。。） 

3五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球。 

1，如果用hash的话，4G的内存不够啊，怎么搞？一个url我们认为是128个字节，那4G内存就只能存1024*1024*1024/128=800万条url

1,内存放不到，可能需要借助外存 

（1），读取文件，计算HASH，按HASH值分段放入不同的文件，文件数可以比较多，两个文件的URL，分开不同的文件放（a1，a2,...，b1，b2，...），保存时可以把HASH值也保存进去，避免再次计算HASH值 

（2），对每一个HASH段，读出两个文件中的一个，比如a1，对HASH值有冲突的放一个连表里，然后读b1文件，取HASH值和URL，如果HASH值在a1中有，则进一步判断URL是否相同。

一般都会想到hash  像你这样分段  是否  a1 要和b1,b2,...bn 都比较看看是否有交集，  a2 也要和b1,b2,...bn 都比较看看是否有交集， 。。。。 

这样好像效率不是很高  百度的面试基本上都要求给出最优的方法。。。 

各位 再想想哈  。。。 

对你们表示感谢。。

a1只需要跟b1比较，因为a1和b1的HASH值在一个段，跟其他的HASH值不在一个段，肯定不会相同的。

分段的意思是说，根据同一个hash算法的结果来划分，比如采用0x0-0xFFFFF作为hash值，将a和b分别拆成1M个文件a_0-a_FFFFF和b_0-b_FFFFF个文件。如果a和b中有相同的url，它们必然处在相同的段里。这样只要a_0和b_0比较，a_1和b_1比较就可以了。平均每个文件包含5000个url，远远低于内存的限制，可以放在内存中运行。此时再使用什么方法，hash也好，排序也好，都不是问题了。该方法中，每个url在硬盘上读2次，写1次，是很高效的。 

如果因为数据分布问题，造成某个段特别大、超出内存范围的话，可对该段再hash一次（当然得换一个hash算法）。如果还不行（比如数千万条相同的url），就对这部分采用硬盘排序等方法。因为它们仅占很小的比例，不会对整体效率造成大的影响。

我能想到的就是对两个文件进行外部排序，然后分别分段读取两个文件的内容逐条比较。将相同的URL写入第三个文件。

第二种算法就是读取第一个文件，算出每条URL的HASHCODE,并把URL和HASHCODE保存到第三个文件的同一行中。第一个文件扫描完成后，对保存HASHCODE的文件和第二个文件进行外部排序，再顺序扫描第二个文件，如果遇到相同的HASHCODE,再比较HASHCODE后面的URL是否相等，如果相等则把此URL输出到第四个文件中。

个人认为对HASHCODE文件和第二个URL文件排序之后，下一条URL的HASHCODE极可能也在HASHCODE文件当前指针的附近，这样会减少对HASHCODE文件的扫描次数，从而提高效率。也可考虑每次从HASHCODE文件的中间部分开始查找，把此文件分成若干分，首先把中间段读入内存，按二分查找查找读入内存中的内容。如果URL的hashcode比读入内存中的最小HASHCODE还小则，把HASHCODE文件的前一段读入内存，否则读入后一段，重复这一过程。考虑到这是本身就是个极占内存的算法，所以不能在内存中实现哈希表算法。本算法最大的困难就是怎样生成重复数最少的哈希码

2.   15个日本鬼子和15个美国鬼子站成一圈，数到9就从圈里面踢出一个来，要求写个程序把日本鬼子都给踢出来， 

美国鬼子都不被踢出来，输出美国鬼子应该站在哪些位置。 

这个题相对更有意思。可以初始化一个三十个元素的字符数组。

char peoples[]=new char[30];

for(int i=8,jc=0;jc<15;i=(i+8)%30)

{

    peoples[i]='j';jc++;

}//所有值是‘j’的位置就是日本鬼子站的地方。

首先按照规则定好日本鬼子应该站的位置，而且从每个日本鬼子的下一人开始数到下一个日本鬼子都正好相差8个人，只需要考虑两个日本鬼子之间的相对位置就好了。每踢出一个，被踢出去的日本鬼子位置会被他后面的那个人代替，所以下一个日本鬼子应该站的位置就是（i+8)%30;