海量数据面试题整理(转).pdfVIP

2011-2-9 海量数据面试题整理（转） - The W… The Way of C++ C++博客 :: 首页 :: 联系 :: 聚合 :: 管理 55 Posts :: 0 Stories :: 16 Comme nts :: 0 Trackbacks 公告 海量数据面试题整理 （转） T he first t ime i use t his blog, i will write something 1. 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制 that i learn whic h i t hink is 是4G，让你找出a、b文件共同的url？ worth write down. 方案1：可以估计每个文件安的大小为50G 64=320G，远远大于内存限制的 常用链接 4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。 我的随笔 我的评论 我参与的随笔 s 遍历文件a，对每个url求取 ，然后根据所取得的值将url分别 存储到1000个小文件 （记为 ）中。这样每个小文件的大约为 留言簿 300M。 给我留言 查看公开留言 s 遍历文件b，采取和a相同的方 将url分别存储到1000各小文件 （记为 查看私人留言 ）。这样处理后，所有可能相同的url都在对应的小文件（ 我参与的团队 ）中，不对应的小文件不可能有相同的url。然后 随笔分类 我们只要求出1000对小文件中相同的url即可。 ACM(21) C/C++(2) s 求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set DataSt ruct And url hash_set 中。然后遍历另一个小文件的每个 ，看其是否在刚才构建的 中，如 Algorithm(2) 果是，那么就是共同的url，存到文件里面就可以了。 Hadoop(5) Java 2 Bloom filter 4G 方案 ：如果允许有一定的错误率，可以使用 ， 内存大概可以表示 Job(2) 340亿bit 。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨 Linux(19) 个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是 Project (1) T opCoder(2) 共同的url （注意会有一定的错误率）。 随笔档案 2. 有10个文件，每个文件1G，每个文件的每一行存放的都是用户的 2010年9月 (6) query，每个文件的query都可能重复。要求你按照query的频度排序。 2010 7 (4) 年 月 2010 5 (1) 方案1： 年 月 2010年4月 (10) 2010年3月 (23) s 顺序读取1