[金山笔试题]现有一块2T硬盘,其中存满了数据,全部是doc文档。根据过往经验,我们推测 其中会有10%(以文件数量计)的文档出现内容重复,但文件名不一定相同,算法用最短的时间,找出所有重复的文件。请在答题纸上用JAVA或其它伪码描述关键算法 。

今天快乐 发布于 2013/07/24 21:46
阅读 6K+
收藏 21

有一2T盘,其中存满了数据,全部是doc文档。根据过往经验,我们推测

其中会有10%(以文件数量计)的文档出现内容重复,但文件名不一定相同:

A.  请设计一个算法:用最短的时间,找出所有重复的文件。请在答题纸上用JAVA或其它伪码描述关键算法

B.  请估算,你提出的这个算法,若要找出这块盘的所有重复文件,

1)  大致需要多少时间(可以你的PC为基准);

2)  峰值内存消耗是多少;

3)  同时请在答题纸描述:

1.  估算的结果(可只给出数量级);

2.  估算的方法;

3.  分析结果的误差范围以及最主要的3个误差来源。

加载中
1
loki_lan
loki_lan
看了大家的这么多回答,竟然都忽略了10%这个重要的东西。
0
beves
beves
坐等高人回答,
0
softsword
softsword
他说的重复应该是完全重复,那重复的文件md5值一定相等
实习导演
实习导演
如果文件的属性不同呢?
小白小霸王
小白小霸王
关键是要快啊,怎么才能快啊
0
117
117

文件名不一定相同暗指文件名相同的话,内容就一定相同么?

那就先找出文件名相同的文件。剩下不相同的文件,根据文件大小分组,然后就先匹配文件内容开头的一点点内容,可以过滤掉一部分文件,再匹配文件中部分的一点点内容,可以过滤一部分文件,最后就是过滤文件尾部分的内容。根据文件数量再选择以上方法进行过滤。最后剩下的部分就全文匹配验证结果。

如果要考虑相同的文件排列格式不一样,导致文件大小不一样就不要根据文件大小进行分组。


具体的答案要好好研究算法导论这本书才行,NND,算法导论我只翻了一点点,这题让我做估计是挂定了。


小k宝贝
小k宝贝
怎么可能文件名不一定相同就暗指了文件名相同,内容就一定相同?这是什么逻辑?脑筋急转弯看多了吧~
罪恶的花生
罪恶的花生
内容相同,文件名不同的,他的文件大小会一样吗?
hlevel
hlevel
等于没说。
今天快乐
今天快乐
恩恩,我现在将文件进行分剪,然后按照分组列表,两两对比
0
乌龟壳
乌龟壳

先找大小相同的文件,没有和它相同则忽略,如果有相同的,再挨个字节比较。

如果是实际解决问题,则会用sqlite来辅助处理,不会在内存上遇到瓶颈,如果确定一定不会在内存大小上遇到问题,则可以把sqlite建在内存中。

今天快乐
今天快乐
用sqlite我倒没有想到啊……(噗,内存是关键啊)
0
把妹达人老张
把妹达人老张

我不会估算时间,内存等,只会写算法。我认为最快的。

1。hashmap,把所有文件md5一下,把md5作为键,绝对路径作为值。

2.把不在hashmap里的value,都删了。

2.2 再做一个hashmap,如果键,在第一个hashmap里,就把这个k—v放在第二个里。把第2个里的value,对应的文件都删了。

3,改善,用hadoop 计算md5更快哦。或者自己写个mapreduce。

nubo
nubo
先读文件长度,只对有重复长度的文件做处理。这样可能过滤掉很多。
s
sysctl
可以先MD4, 有重复再md5, 快很多
今天快乐
今天快乐
我也想到了mapreduce……这样能效率稍高点(毕竟前期是2T数据,hadoop不就是1T以上数据开始占优势的吗)
泡不烂的凉粉
泡不烂的凉粉
hash 方法最慢, 因为要读取所有内容.应该首先被排除掉.
0
Duziee
Duziee
硬盘的2TB是按照工业标准来的吧,是1000X1000X1000X1000B=1TB
0
雨翔河
雨翔河
内容重复的话,匹配是否相同的时候用KMP算法。只想到了这个。
0
明月照大江
明月照大江

找出内容重复的doc文档。

第一,文件内容长度筛选,先将所有的文件,按照文件内容长度进行归类。对于某一长度只有一个文件,则该文件无重复。文件内容长度是文件属性的一部分,不用拿出内容就可以得到了。

第二,以长度为分组,一组一组地进行组内筛选,对每一组的文件,取出 64个字节(根据硬盘的格式和块大小),最好不是文件头或者尾巴,应当是文件中间的数据,即一次性取出的最小字节序列(总之怎么快怎么取),进行hash运算。可以排除出大多数长度一致,但是内容不一致的文件。(使用hash表,一旦散列出现冲突,则文件为重复的,记录下文件就好)

第三,对于上一步骤64个字节都一样的文件,如果文件内容长度比较长,就进行首部,中间,尾部等,多个位置进行取样hash,如果两个文件相同,那么取样hash一定相同,这个是防止出现文件大部分数据相同的情况。做法如上

第四,对于上一步还相同的文件,进行全文hash。

1.时间估计,这个真不好估计

2.峰值内存,因为内存中,不需要存储文件的内容,只需要存储文件的hash和文件的名称,也没有临时文件的产生,用得不多。具体用多少不知道。

。大体思路就是这样

明月照大江
明月照大江
回复 @liqiang1226 : 编码也就能写个伪代码了~
liqiang1226
liqiang1226
感觉说得不错,但是原题需要编码哦。。 求大神编一段学习一些。。
nubo
nubo
这个不错的。关于内存和耗时,可以通过对不同位置,固定长度取样的算法估算。
0
姑妄听之
姑妄听之
这题目挺有意思。
返回顶部
顶部