一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3053|回复: 25
收起左侧

请教一道dropbox经典老题,duplicate files

[复制链接] |试试Instant~ |关注本帖
Kelsey_Xu 发表于 2016-2-21 15:42:00 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Dropbox - 内推 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
各位大牛们,后天要面dropbox了,看地里很多人都碰到了duplicate files这道题。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

大家的讨论各异,但还是不太明白这题具体的解决思路。

好像正确解法是用DFSBFS获得全部files in a directory,然后根据file metadata来分类,然后hash。我不太明白如何根据file metadata来分类


求哪位面过dropbox的大神指导一下思路~多谢多谢!

. 1point 3acres 璁哄潧

autumnhu 发表于 2016-2-22 04:38:30 | 显示全部楼层
这题关键不是考你的BFS或者DFS,虽然你需要用BFS或者DFS先把所有文件先找出来。找出来之后怎么除重才是真正他们想考你的地方。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
最简单的方法:
用MD5 hash值做hashmap的key,然后对key相同的文件两两比较(所以MD5有可能会碰撞,所以需要double check)
这样做的坏处:就算目录里只有少量的duplicated的文件,每个文件都还是需要从头到尾扫描一遍(计算MD5)。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
改进的办法:
可以先按照size分组,再按照前1K个bytes作为hashmap的key将文件分组,然后每个文件数不少于2的组按照[1K+1, 2K]这接下来的1K个bytes分组……然后按照这个思路一直分下去。. visit 1point3acres.com for more.
这样做的好处:在现实中,一般目录里面大部分的文件都是unique的,只有少量duplicate,在这个逐层分组的过程中,大量的文件都会在前几步的分组里面被分到一个只有它自己的组里,对于这些文件,我们就已经不再需要扫描它后面的部分。
回复 支持 4 反对 0

使用道具 举报

autumnhu 发表于 2016-10-19 13:25:54 | 显示全部楼层
liurudahai 发表于 2016-9-30 23:06
还有MD5如果要写CODE话要怎么写?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
就写个伪代码getMD5(File);就好了
回复 支持 1 反对 0

使用道具 举报

carthus 发表于 2016-2-21 23:22:06 | 显示全部楼层

回帖奖励 +2

我觉得就先拿个size分分类就好了。。。然后再拿前100个bytes来hash一下再分类,然后byte to byte地比较两个文件,我还没面。。
回复 支持 1 反对 0

使用道具 举报

 楼主| Kelsey_Xu 发表于 2016-2-22 01:13:49 | 显示全部楼层
carthus 发表于 2016-2-21 23:22
我觉得就先拿个size分分类就好了。。。然后再拿前100个bytes来hash一下再分类,然后byte to byte地比较两个 ...

哈 我记得咱俩基本同时拿到的电面啊! 加油了
回复 支持 反对

使用道具 举报

 楼主| Kelsey_Xu 发表于 2016-2-22 01:15:09 | 显示全部楼层
carthus 发表于 2016-2-21 23:22
我觉得就先拿个size分分类就好了。。。然后再拿前100个bytes来hash一下再分类,然后byte to byte地比较两个 ...

这道题是说:同一目录下,有duplicate files,但文件名不一样,内容啥的都一样,然后让找到这些文件吗?
回复 支持 反对

使用道具 举报

carthus 发表于 2016-2-22 02:31:25 | 显示全部楼层
Kelsey_Xu 发表于 2016-2-22 01:15
这道题是说:同一目录下,有duplicate files,但文件名不一样,内容啥的都一样,然后让找到这些文件吗?

对的对的
回复 支持 反对

使用道具 举报

wcyz666 发表于 2016-2-22 02:44:46 | 显示全部楼层
用MD5 hash值做hashmap的key?
回复 支持 反对

使用道具 举报

tktrung 发表于 2016-2-22 08:10:35 | 显示全部楼层
autumnhu 发表于 2016-2-22 04:38
这题关键不是考你的BFS或者DFS,虽然你需要用BFS或者DFS先把所有文件先找出来。找出来之后怎么除重才是真正 ...

这题如果说我用python,是不是要写个python代码把从头到尾做出来,还是讲一下想法就行啊
回复 支持 反对

使用道具 举报

carthus 发表于 2016-2-22 09:04:34 | 显示全部楼层
哎顺便问一下,你知道phone number combination那题,面经里他们说一个follow up是用trie tree 到底该怎么用?
回复 支持 反对

使用道具 举报

 楼主| Kelsey_Xu 发表于 2016-2-22 09:12:37 | 显示全部楼层
autumnhu 发表于 2016-2-22 04:38
这题关键不是考你的BFS或者DFS,虽然你需要用BFS或者DFS先把所有文件先找出来。找出来之后怎么除重才是真正 ...

谢谢大神!
回复 支持 反对

使用道具 举报

 楼主| Kelsey_Xu 发表于 2016-2-22 09:13:29 | 显示全部楼层
carthus 发表于 2016-2-22 09:04
哎顺便问一下,你知道phone number combination那题,面经里他们说一个follow up是用trie tree 到底该怎么 ...

面经里不是说trie比dict慢吗,面试官提示的用cache,保存结果。虽说我也没太懂这是啥意思。。。
回复 支持 反对

使用道具 举报

carthus 发表于 2016-2-22 15:16:19 | 显示全部楼层
Kelsey_Xu 发表于 2016-2-22 09:13
面经里不是说trie比dict慢吗,面试官提示的用cache,保存结果。虽说我也没太懂这是啥意思。。。

啥cache……不懂,有另一个面经 他也说了trie 一个很早的面经
回复 支持 反对

使用道具 举报

 楼主| Kelsey_Xu 发表于 2016-2-23 00:24:54 | 显示全部楼层
carthus 发表于 2016-2-22 15:16
啥cache……不懂,有另一个面经 他也说了trie 一个很早的面经

求那个很早的面经链接~
回复 支持 反对

使用道具 举报

carthus 发表于 2016-2-23 01:00:42 | 显示全部楼层
Kelsey_Xu 发表于 2016-2-23 00:24. more info on 1point3acres.com
求那个很早的面经链接~

http://www.1point3acres.com/bbs/ ... adio%26sortid%3D311. from: 1point3acres.com/bbs
最后他说了一句
回复 支持 反对

使用道具 举报

singledog2016 发表于 2016-5-18 12:18:44 | 显示全部楼层
楼主 这题你有代码吗 看看 感觉代码写起来很难。。。
回复 支持 反对

使用道具 举报

 楼主| Kelsey_Xu 发表于 2016-5-20 01:04:14 | 显示全部楼层
singledog2016 发表于 2016-5-18 12:18. 1point3acres.com/bbs
楼主 这题你有代码吗 看看 感觉代码写起来很难。。。

不好意思 我当时面试完了,忘记保存了。。但可以告诉你,地里的答案都不太完整,如果自己不改的话,应该是过不了面试的
回复 支持 反对

使用道具 举报

Yoyo00 发表于 2016-5-20 02:26:10 | 显示全部楼层
Kelsey_Xu 发表于 2016-5-20 01:04
不好意思 我当时面试完了,忘记保存了。。但可以告诉你,地里的答案都不太完整,如果自己不改的话,应该 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
可以说一下大致的思路吗?
我看地里说的基本是hashsum判断文件重复,再加上根据size判断。还有别的遗漏的方法没有?多谢!
回复 支持 反对

使用道具 举报

cattney 发表于 2016-8-25 13:37:21 | 显示全部楼层
有大神做过Grid Illumination的OA吗!!
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-9-30 23:05:02 | 显示全部楼层
autumnhu 发表于 2016-2-22 04:38
这题关键不是考你的BFS或者DFS,虽然你需要用BFS或者DFS先把所有文件先找出来。找出来之后怎么除重才是真正 ...

这题到底是设计题还是CODING题
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-9-30 23:06:55 | 显示全部楼层
autumnhu 发表于 2016-2-22 04:38
这题关键不是考你的BFS或者DFS,虽然你需要用BFS或者DFS先把所有文件先找出来。找出来之后怎么除重才是真正 ...

还有MD5如果要写CODE话要怎么写?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 10:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表