算法
求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。
方案2:如果允许有一定的错误率,可以使用Bloom filter,4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。
Bloom filter日后会在本BLOG内详细阐述。
6、在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数。
方案1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。
方案2:也可采用与第1题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。
7、腾讯面试题:给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
与上第6题类似,我的第一反应时快速排序+二分查找。以下是其它更好的方法:
方案:oo,申请512M的内存,一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。 dizengrong:
这个问题在《编程珠玑》里有很好的描述,大家可以参考下面的思路,探讨一下: 又因为2^32为40亿多,所以给定一个数可能在,也可能不在其中;
这里我们把40亿个数中的每一个用32位的二进制来表示
假设这40亿个数开始放在一个文件中。
然后将这40亿个数分成两类:
1.最高位为0
2.最高位为1
并将这两类分别写入到两个文件中,其中一个文件中数的个数<=20亿,而另一个>=20亿(这相当于折半了);
与要查找的数的最高位比较并接着进入相应的文件再查找
再然后把这个文件为又分成两类:
1.次最高位为0
2.次最高位为1
并将这两类分别写入到两个文件中,其中一个文件中数的个数<=10亿,而另一个>=10亿(这相当于折半了);
与要查找的数的次最高位比较并接着进入相应的文件再查找。
.......
以此类推,就可以找到了,而且时间复杂度为O(logn)
十道海量数据处理面试题与十个方法大总结_IT/计算机_专业资料。2011/5/9 十道海量数据处理面试题与十个方法…欢迎 in7deforever 我的: 空间 欢迎 in7deforever! ...
十道海量数据处理面试题与十个方法大总结_信息与通信_工程科技_专业资料。第一部分为10道海量数据处理的面试题,第二部分为10个海量数据处理的方法总结。海量...
此文, 却无任何收获, 那么, 我也甘愿背负这样的罪名, :-), 同时, 此文可以看做是对这篇文章: 十道海量数据处理面试题与十个方法大总结的一般抽象 性总结。 ...
前言本博客内曾经整理过有关海量数据处理的 10 道面试题 (十道海量数据处理面试题与十个 方法大总结),此次除了重复了之前的 10 道面试题之后,重新多整理了 7...
如果读者读罢此文,却无任何收获,那么,我也甘愿背负这样的罪名,:-),同时,此文可以看做是对 这篇文章:十道海量数据处理面试题与十个方法大总结的一般抽象性总结。...
此文, 却无任何收获, 那么, 我也甘愿背负这样的罪名, :-), 同时, 此文可以看做是对这篇文章: 十道海量数据处理面试题与十个方法大总结的一般抽象 性总结。 ...
教你如何迅速秒杀99%的海量数据处理面试题_IT/计算机_专业资料。十道海量数据处理面试题与十个方法大总结的一般抽象性总结教你如何迅速秒杀99%的海量数据处理面试题...
前言本博客内曾经整理过有关海量数据处理的 10 道面试题(十道海量数据处理面试题与十个方法大总结), 此次除了重复了之前的 10 道面试题之后,重新多整理了 7 ...
”-- 十道海量数据处理面试题与十个方法大总结。 注:Hash 取模是一种等价映射,不会存在同一个元素分散到不同小文件中 去的情况,即这里采用的是 mod1000 ...
如果读者读罢此文, 却无任何收获, 那么, 我也甘愿背负这样的罪名, :-), 同时, 此文可以看做是对这篇文章: 十道海量数据处理面试题与十个方法大总结的一般抽象...
,如果读者读罢此文,却无任何收获,那么,我也甘愿背负这样的罪名,:-),同时,此文可以看做是对这篇文章:十道海量数据处理面试题与十个方法大总结的一般抽象性总结。...
”--十道海量数据处理面试题与十个方法大总结。 关于本题,还有几个问题,如下: 1、Hash 取模是一种等价映射,不会存在同一个元素分散到不同小文件中去的情况,...
热门文档