面试题讨论：如何在一批文件中找到相同的文件 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

面试题讨论：如何在一批文件中找到相同的文件

面试题讨论：如何在一批文件中找到相同的文件# JobHunting - 待字闺中

x*i2013-10-15 07:10

1 楼

原题是 http://www.mitbbs.com/article_t/JobHunting/32549243.html。
里面提到的思路是先排序文件大小，然后比较文件内容hash.
大家有没有别的思路呀？

w*s2013-10-15 07:10

2 楼

hash思路应该是比较efficient了吧？

b*e2013-10-15 07:10

3 楼

指点下为什么要排序？直接往dictionary里加是O(n)，排序是O(nlog(n))。直接加不
是要快点？

a*e2013-10-15 07:10

4 楼

我觉得按文件大小排序和读硬盘的时间相比基本可以忽略不计。
不过Hash在这里确实比排序更快点儿。

【在 b*******e 的大作中提到】

: 指点下为什么要排序？直接往dictionary里加是O(n)，排序是O(nlog(n))。直接加不
: 是要快点？

b*52013-10-15 07:10

5 楼

按size排序，和dictionary hash，这两个N，不一样。如果size不一样，你根本
就不需要hash，就知道这两个文件不一样了

【在 b*******e 的大作中提到】

: 指点下为什么要排序？直接往dictionary里加是O(n)，排序是O(nlog(n))。直接加不
: 是要快点？

b*e2013-10-15 07:10

6 楼

倆dictionary,hash size 分类先，hash内容再分类。还是比O(nlog(n))要快。而且如
果相同size文件不多的话，这个会很快。

u*o2013-10-15 07:10

7 楼

觉得题有点眼熟呢，原来是我的帖子。。
我被VMWARE拒掉了，不知是思路不对还是题没答完的原因，可能两者都有吧。
不过发现这种hot startup实在是难啊，1个小时满满一页的题！都是做ACM出身的吧才
能答出来吧。。不适合挫人练手呀。

d*n2013-10-15 07:10

8 楼

VMWARE怎么能叫hot startup呢

h*o2013-10-15 07:10

9 楼

文件怎么hash？谁是key谁是value?

【在 b*******e 的大作中提到】

: 倆dictionary,hash size 分类先，hash内容再分类。还是比O(nlog(n))要快。而且如
: 果相同size文件不多的话，这个会很快。

A*o2013-10-15 07:10

10 楼

看MD5 digest，相当于做个hash join

【在 x*******i 的大作中提到】

: 原题是 http://www.mitbbs.com/article_t/JobHunting/32549243.html。
: 里面提到的思路是先排序文件大小，然后比较文件内容hash.
: 大家有没有别的思路呀？

b*e2013-10-15 07:10

11 楼

能用openssl hash么？

c*d2013-10-15 07:10

12 楼

hash 能判断两文件是否完全相同。
如果改一下题目，在一批文件中找相似（但不完全相同）文件呢？有什么好想法？

【在 x*******i 的大作中提到】

: 原题是 http://www.mitbbs.com/article_t/JobHunting/32549243.html。
: 里面提到的思路是先排序文件大小，然后比较文件内容hash.
: 大家有没有别的思路呀？

s*u2013-10-15 07:10

13 楼

还是类似的吧。
其实这个就是下面这个题的变种：
两个数组，找最接近的一对数字。解法就是分别排序，然后用两个指针，i =0； j = 0
;开始往后遍历。如果j对应的数字偏大，那么就i++；反之j++。
对文件的话，应该就是将hash值以某种方法排序，比如数值序或者词典序。

【在 c***d 的大作中提到】

: hash 能判断两文件是否完全相同。
: 如果改一下题目，在一批文件中找相似（但不完全相同）文件呢？有什么好想法？

c*d2013-10-15 07:10

14 楼

这就不是正常的hash了。
传统意义上的hash要求即使源做很小的改动，目标hash值也有巨大变化，尽量要求hash
值与源不相关。
对hash值进行排序没意义呀。

0

【在 s********u 的大作中提到】

: 还是类似的吧。
: 其实这个就是下面这个题的变种：
: 两个数组，找最接近的一对数字。解法就是分别排序，然后用两个指针，i =0； j = 0
: ;开始往后遍历。如果j对应的数字偏大，那么就i++；反之j++。
: 对文件的话，应该就是将hash值以某种方法排序，比如数值序或者词典序。

s*u2013-10-15 07:10

15 楼

那就只好找能够反映源的变化程度的hash办法了。

hash

【在 c***d 的大作中提到】

: 这就不是正常的hash了。
: 传统意义上的hash要求即使源做很小的改动，目标hash值也有巨大变化，尽量要求hash
: 值与源不相关。
: 对hash值进行排序没意义呀。
:
: 0