~/problems / Files & networks / File deduplication

Find duplicate files (size, prefix, content)

medium 3 levels ~55 min Anthropic

Level 1 Group duplicate files

Implement find_duplicate_files(root_path: str) -> list[list[str]].

  • Walk the directory tree under root_path recursively with os.walk. Build each path as os.path.join(dirpath, filename).
  • Return every group of two or more regular files whose contents are byte-for-byte identical. Files without a duplicate don't appear at all. Sort the paths inside each group, and sort the list of groups.
  • Skip symbolic links (to files or to directories; os.walk doesn't descend into linked directories by default).
  • Empty files are duplicates of each other: all zero-byte files form one group.
  • Unreadable files must not crash the walk. If opening or reading a file raises OSError (such as PermissionError), leave that file out.

Be efficient, because real trees hold large files:

  1. Bucket the files by size first (os.path.getsize). A file whose size is unique can't have a duplicate, so never open it.
  2. For the files that share a size, hash their contents with hashlib.sha256, reading in chunks (64 KiB is a good size, never more than 1 MiB per read) instead of reading a whole file at once.
  3. Files with the same (size, digest) are duplicates.

Open files with the built-in open(path, "rb"); the tests watch it to see which files you read and how much.

# tree:  a.txt "hello"   sub/b.txt "hello"   c.txt "hellp"   d "" (empty)   e ""
find_duplicate_files(root)
# [[root/a.txt, root/sub/b.txt], [root/d, root/e]]

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Topic: File deduplication. Group by size, then hash; walk directories.

0:00
Ctrl ' run · Ctrl ↵ submit
esc