面试题，大规模url求重复讨论 - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 面试题，大规模url求重复讨论

相关主题
● 在线紧急求助一道system design面试题，面经内附	● 问一道面试题，现在好像很流行这种题
● 一个google面试题	● 如何秒杀99%的海量数据处理面试题
● 问一个bloom filter 和 bitmap的使用区别	● 新鲜面试题
● 贡献个teableau的昂赛面经	● 某大公司面试题
● 问个mutex的面试题	● 面试: Take home project
● 问问谁会这道算法的面试题？	● 亚马逊电话第二轮
● 请教一个面试题	● 考古G面经里两道题
● 贡献一下：本版上搜集的 Google 面试题	● HashTable相关的面试题

相关话题的讨论汇总
话题: url话题: hash话题: 文件话题: 面试题话题: 解法

进入JobHunting版参与讨论

1

(共1页)

I********T 发帖数: 22	1 看到一道面试题给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出共同的URL。这个题目在网上看到有两种解法：解法一：（1），读取文件，计算HASH，按HASH值分段放入不同的文件，文件数可以比较多，两个文件的URL，分开不同的文件放（a1，a2,...，b1，b2，...），保存时可以把HASH值也保存进去，避免再次计算HASH值（2），对每一个HASH段，读出两个文件中的一个，比如a1，对HASH值有冲突的放一个连表里，然后读b1文件，取HASH值和URL，如果HASH值在a1中有，则进一步判断URL是否相同。解法二：Bloom Filter（广泛应用于URL过滤、查重。参考 http://en.wikipedia.org/wiki/Bloom_filter、 http://blog.csdn.net/jiaomeng/archive/2007/01/28/1496329.aspx）可是我算了下内存4G，换成bit位是4 * 2^30 * 8 =32 2^30 个位，数据有52^30, 这样把全部内存用来做h
I********T 发帖数: 22	2 而且bloom filter 不是和我的方法没什么差别么? 。。
I********T 发帖数: 22	3 有没大牛指点一下。。

1

(共1页)

进入JobHunting版参与讨论

相关主题
● HashTable相关的面试题	● 问个mutex的面试题
● 半小时之前的G电面，估计挂了	● 问问谁会这道算法的面试题？
● 面试题讨论：如何在一批文件中找到相同的文件	● 请教一个面试题
● 几道marvell面试题	● 贡献一下：本版上搜集的 Google 面试题
● 在线紧急求助一道system design面试题，面经内附	● 问一道面试题，现在好像很流行这种题
● 一个google面试题	● 如何秒杀99%的海量数据处理面试题
● 问一个bloom filter 和 bitmap的使用区别	● 新鲜面试题
● 贡献个teableau的昂赛面经	● 某大公司面试题

相关话题的讨论汇总
话题: url话题: hash话题: 文件话题: 面试题话题: 解法

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)