题目重点：递归枚举文件，并讨论分散在百台机器上的相同内容。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 目录为静态快照，仅普通文件，跳过符号链接；同inode的hard link别名只算一个对象。
- “重复”指完整字节相等，不是文件名相同或相似图片；返回每组路径，不删除任何文件。
解题路线
- 先size分组，单文件size组不用读内容。同size组流式SHA256，避免完整文件进内存；随后对同digest候选与代表逐字节比较，保证即使hash碰撞仍精确。
- 共享一个hash不等于绝对相同，代码通过强制digest碰撞测试验证不会误组。零字节文件也能正确分组；遍历失败、权限和文件在读取中变化需生产错误策略，本示例依静态快照前提。
- 百机先本地size/digest，元数据按(size,digest)分片路由，owner合并候选并跨机比字节；普通情形少传大文件，恶意碰撞则可能较多传输。owner故障/重复报告用fileID+version去重，先发现后再另行审批任何删除。
手动走一遍
同名不同内容不重复，异名同内容进同一组。大小相同hash相同但字节不同，最终分为不同组；文件内容修改则旧fingerprint失效。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from pathlib import Path
from collections import defaultdict
import hashlib,os
def fingerprint(path,chunk=65536):
digest=hashlib.sha256()
with open(path,'rb') as stream:
while data:=stream.read(chunk):digest.update(data)
return digest.digest()
def equal_files(a,b,chunk=65536):
with open(a,'rb') as left,open(b,'rb') as right:
while True:
x,y=left.read(chunk),right.read(chunk)
if x!=y:return False
if not x:return True
def duplicates(root,digest=fingerprint):
# Static directory tree; symlinks excluded, hard-link aliases one identity.
by_size=defaultdict(list);identities=set()
for directory,_,names in os.walk(root,followlinks=False):
for name in names:
path=Path(directory)/name
if path.is_symlink() or not path.is_file():continue
stat=path.stat();identity=(stat.st_dev,stat.st_ino)
if identity in identities:continue
identities.add(identity);by_size[stat.st_size].append(str(path))
answer=[]
for paths in by_size.values():
if len(paths)<2:continue
by_digest=defaultdict(list)
for path in sorted(paths):by_digest[digest(path)].append(path)
for candidates in by_digest.values():
exact=[]
for path in candidates:
group=next((g for g in exact if equal_files(g[0],path)),None)
if group is None:exact.append([path])
else:group.append(path)
answer.extend(g for g in exact if len(g)>1)
return sorted(answer)
复杂度
n文件、需读总字节B，通常O(n+B)加路径排序，chunk固定辅助缓冲。强制hash碰撞组逐代表比对最坏多次扫文件，保守O(nB)，路径/元数据O(n)。
易错点与追问
容易失分的边界
- 硬链接是否算两个重复路径必须先定，不能用数量混淆存储释放量。
- 读一次size再另时读内容而文件持续变化会使证据不一致。
继续深挖
- 跨机路径复用时怎么定义fileID和版本？
- 只看prefix hash如何加速候选筛选而仍保证完整确认？
