Quick Overview

Implement streaming file deduplication that filters by size, fingerprint and hash, then compares bytes to rule out hash collisions. It covers large-file chunking, batched disk I/O, parallelizing across cores or machines, a dry-run report, and hard links that never cross devices. Follow-ups turn it into a command-line tool that handles symbolic links, unreadable files, error cases, and options to move or delete duplicates.

Implement file deduplication at scale

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Write a program to deduplicate files in a very large directory tree. Identify groups of identical files without loading entire files into memory. Outline your approach to hashing (e.g., size filter, partial hash, full hash), chunking for very large files, and handling hash collisions. Support a mode that replaces duplicates with hard links (when safe) and a dry-run report of duplicate sets. Explain time and space complexity, how you batch disk I/O, and how you would parallelize across CPU cores or machines.

Overview: Implement streaming file deduplication that filters by size, fingerprint and hash, then compares bytes to rule out hash collisions. It covers large-file chunking, batched disk I/O, parallelizing across cores or machines, a dry-run report, and hard links that never cross devices. Follow-ups turn it into a command-line tool that handles symbolic links, unreadable files, error cases, and options to move or delete duplicates.

Read the full Anthropic Software Engineer interview experience this question came from

Implement `solution(files, mode)`, a file-deduplication pipeline that finds files with identical content and, in `link` mode, reports the hard-link operations to deduplicate them. **Input.** `files` is a list of 4-tuples `(path, device_id, inode_id, chunks)`. `path` is unique; `device_id` is the file's device; `inode_id` is its inode (files sharing an `inode_id` are already hard-linked); `chunks` is a list of strings whose concatenation in order is the content (chunks may be empty; the list may be empty). `mode` is `'report'` or `'link'`. Walk the chunks directly; never concatenate a whole file into one big string. **Duplicates.** Two files are duplicates when their reconstructed content is exactly equal (chunk boundaries don't matter: `['hello','world']` equals `['helloworld']`). A duplicate **set** is a maximal collection of 2+ content-equal files; unmatched files aren't reported. **Output.** Return a 2-tuple `(groups, links)`. `groups`: a list of duplicate sets; each set is its paths sorted lexicographically; only sets of 2+ are included; sets are ordered by their smallest (first) path. `links`: `[]` in `'report'` mode. In `'link'` mode, per set, handle each device separately: links are valid only within the same `device_id`. On a device, the lexicographically smallest path among that set's files there is the canonical target; for every other file on that device, emit `(path, canonical_path)` only if its `inode_id` differs from the canonical's. Sort the final `links` ascending. **Constraints.** `0 <= len(files) <= 200000`; `0 <= total characters across all chunks <= 1000000`; each `path` is unique; `mode` is `'report'` or `'link'`. **Example.** `[('/a',1,100,['hello','world']),('/b',1,101,['helloworld']),('/c',2,200,['hello','world']),('/d',1,102,['hello','there'])]` in `'link'` mode returns `([['/a','/b','/c']], [('/b','/a')])`. **Follow-up discussion (not graded).** None of this changes the graded function: `mode` is still only `'report'` or `'link'`, and each file is still the 4-tuple described above. Be ready to discuss how you would turn the pipeline into a command-line tool that runs on a real directory tree: - how it enumerates the tree recursively with `os`/`pathlib` primitives, and how it treats symbolic links; - how it reads file contents from disk, and the memory and disk-I/O trade-offs on very large files; - how it handles permissions: files or directories it cannot read, and what it needs before it can replace a file with a hard link; - which error cases it must handle, both while scanning and while acting on a duplicate set; - how it outputs duplicate groups, with options to move or delete duplicates as well as hard-link them, and what safeguards those options need; - how it would parallelize the scan and hashing across CPU cores, and split the work across machines.

Constraints

  • 0 <= len(files) <= 200000
  • 0 <= total number of characters across all chunks <= 1000000
  • Each `path` is unique
  • `mode` is either `'report'` or `'link'`

Examples

Input: ([('/a', 1, 100, ['hello', 'world']), ('/b', 1, 101, ['helloworld']), ('/c', 2, 200, ['hello', 'world']), ('/d', 1, 102, ['hello', 'there'])], 'link')

Expected Output: ([['/a', '/b', '/c']], [('/b', '/a')])

Explanation: Files /a, /b, and /c have identical content even though /a and /b use different chunk boundaries. Only /b can be hard-linked to /a because /c is on a different device.

Input: ([('/e', 1, 10, []), ('/f', 1, 11, []), ('/g', 1, 20, ['x']), ('/h', 1, 20, ['x']), ('/i', 1, 21, ['x'])], 'link')

Expected Output: ([['/e', '/f'], ['/g', '/h', '/i']], [('/f', '/e'), ('/i', '/g')])

Explanation: Empty files /e and /f are duplicates, so /f can link to /e. Files /g, /h, and /i are duplicates; /h already shares /g's inode, so only /i needs a hard-link operation.

Hints

  1. Use increasingly expensive filters: size, then a small content-based prefix/suffix fingerprint, then a full streaming hash.
  2. A matching full hash is not enough for absolute correctness. Compare the actual streamed contents inside a full-hash bucket to handle collisions and different chunk boundaries.

Loading coding console...

Show the approach

Approach

The solution runs a four-stage cascade, mirroring real dedup systems, and never concatenates a whole file — sizes, fingerprints, hashes, and final equality checks all walk the chunks list directly.

Setup. Each file becomes a record {path, device, inode, chunks, size}, where size is sum(len(chunk)) (no string built).

Stage 1 — size. Records are bucketed by size (size_groups). Files of different sizes can't be duplicates, so any size group of fewer than 2 is dropped — a cheap filter that kills most pairs.

Stage 2 — partial fingerprint. Within a size group, records are re-keyed by (size, first_16, last_16). first_k/last_k pull the leading and trailing 16 characters by stepping across chunk boundaries (and skipping empty chunks), so a tiny prefix/suffix distinguishes most non-duplicates without hashing.

Stage 3 — full streaming hash. Surviving candidates get a blake2b digest computed incrementally, h.update per chunk. Equal digests are grouped.

Stage 4 — collision-safe verify. Because a hash match isn't a proof, each digest group is split into collision_safe_groups: a two-pointer same_content compares the two files chunk-by-chunk (handling mismatched chunk boundaries) so only byte-identical files share a bucket. Buckets of size ≥ 2 become confirmed duplicate sets.

Output. Each set's paths are sorted; sets are ordered by their first path. In link mode, each set is split per device (hard links can't cross device_id); on each device the lexicographically smallest path is the canonical target, and a (path, canonical) link is emitted only when the file's inode differs (same inode = already linked). Links are returned sorted. This is correct because equality is verified, and linking respects device and existing-inode constraints.

Follow-up discussion (not graded). The graded function starts from an already-enumerated list of (path, device_id, inode_id, chunks) tuples. A real command-line tool puts a filesystem walk in front of the same four-stage cascade and a guarded action step behind it.

Walking the tree. Use os.scandir with an explicit stack of directories instead of recursion, so a very deep tree can't hit Python's recursion limit (os.walk is built on scandir but is itself recursive before Python 3.12). pathlib works too, but scandir usually gets each entry's type from the directory listing without an extra system call. On POSIX, entry.stat(follow_symlinks=False) gives the size plus st_dev and st_ino, which are exactly the graded device_id and inode_id (on Windows DirEntry.stat leaves both at 0, so call os.lstat on the path there). Only regular files become candidates: sockets, FIFOs and device nodes are skipped (opening a FIFO can block forever), and paths that already share (st_dev, st_ino) are one file with several names, so its content is read once.

Symbolic links. Don't follow them by default. A symlink stores a path, not the data, so it is never a duplicate itself. If the walk followed it, the link and its target would read as identical content, and acting on that pair is how data gets lost: keeping the link and deleting the real file destroys the only copy and leaves a dangling link, and moving the real file away leaves the link dangling too. Linking is just as fragile. Python's os.link follows a symlink source by default and links its target, but with follow_symlinks=False (or the raw link call on Linux) it hard-links the symlink itself, so replacing the real file with that link frees the real file's data and leaves a second copy of the symlink in its place. unlink and rename on a link's path act on the link, not on its target. Skipping links to files and not descending into linked directories also rules out cycles (a link pointing at an ancestor) and subtrees counted twice. If the user opts in with a flag such as --follow-symlinks, keep a visited set of directory (st_dev, st_ino) pairs to break loops, key files by their target's (st_dev, st_ino) so each is hashed once, and act only on real file paths, never on the link.

Memory and disk I/O. Read files in fixed-size blocks (roughly 64 KiB to 1 MiB) with open(path, 'rb'), so each worker holds one buffer whatever the file size; the chunks list models exactly that. Stage 1 opens no file, because the size comes from the walk's stat. Stage 2 reads only a few KiB from each end of a file, so most non-duplicates cost two small reads. Only the survivors are read in full, sequentially, which suits both spinning disks and SSDs, and ordering reads by directory or inode number cuts seeks further on spinning disks. Stage 4 can compare a whole hash group in lockstep, one block per file at a time, so each file is read only once more. A practical split is to trust a 256-bit hash for the report and compare bytes only right before linking or deleting (replacing a file whose st_nlink is 1 with a link frees its data, so linking is destructive too), where the comparison doubles as the freshness check below. After the walk, keep metadata only for sizes shared by two or more files, since per-file metadata is the other memory cost on trees with millions of entries.

Permissions. scandir, stat and open can each raise PermissionError or another OSError. Catch it per entry, add the path and reason to a skipped list, and keep walking: one unreadable directory must not abort the scan, and an unreadable file is never a candidate because its content can't be proven equal. Print the skipped count with the report and exit nonzero when anything was skipped. Replacing a duplicate with a hard link needs write and search permission on the directory that holds it, not write permission on the file. A sticky directory such as /tmp also requires owning the file or the directory, and Linux (fs.protected_hardlinks) can refuse to link to a file the user neither owns nor has read and write access to. Hard links share one inode, so afterwards every path has the canonical file's owner, group, mode and timestamps, and a write through one path changes all of them. The safe default is to link only files whose owner, group and mode match, and report the rest.

Error cases. Each one is handled per file, recorded, and skipped, so a single failure never stops the run:

  • Changed or vanished after hashing. Right before acting, lstat both the duplicate and the canonical file again and require the scan-time st_dev, st_ino, size and st_mtime_ns; before linking or deleting, compare contents again too. Skip on any difference, and on ENOENT.
  • Failure partway through a replace. os.link refuses to overwrite a name, so create the link under a temporary name in the same directory, then call os.replace(tmp, duplicate), which swaps the name atomically: the path always holds either the old file or the new link. Remove the temporary name if the rename fails, and also if it still exists afterwards (rename does nothing when both names already share an inode). A crash between os.link and os.replace leaves the temporary name behind as an extra hard link to the canonical file, so give it a recognizable form (for example .dedup-tmp-PID-N), skip such names during the walk, and at the start of the next run remove any leftover whose st_nlink is above 1.
  • EXDEV. Grouping by device_id prevents most cross-filesystem links, but Linux also returns it between two bind mounts of the same filesystem.
  • EMLINK. The canonical inode has hit the filesystem's link-count limit (65,000 on ext4); promote another member to a second canonical file, or stop linking that set.
  • EROFS, EACCES/EPERM, ENOSPC, and EIO while hashing. Skip the file or the set and record why.

Apart from that temporary name, every step leaves either the original file or a correct link in place, so rerunning after an interruption is safe: files that are already linked share an inode and get no new link, exactly as in the graded function.

Output and actions. The default is the dry-run report: each duplicate set with its size, hash, paths and the space it would free, counting space only when an inode's last name goes away (st_nlink), since a path whose inode has other names outside the tree frees nothing. Changing anything takes an explicit flag (--link, --move DIR, --delete) and a deterministic keep policy (the graded rule keeps the smallest path; the oldest file or a path under a preferred root also work), so a dry run and a real run pick the same survivor.

  • Move sends duplicates to a quarantine directory that mirrors their relative paths, so names can't collide and undoing is a move back. On the same filesystem that is one atomic os.rename; across filesystems it is copy, fsync, verify, then unlink the source, never the other way round.
  • Delete needs its own flag (ideally with a confirmation prompt), repeats the pre-action re-check, never deletes a file whose kept copy is a symlink or a path that runs through a symlinked directory, and never removes the last copy: before each unlink, confirm the kept file still exists and still matches.
  • Every action is appended to a journal (action, path, kept path, size, hash, and the path's original owner, group, mode and st_mtime_ns) before it runs, so a run can be audited and undone. A move is undone by moving the file back. A link is undone by copying the kept content to a temporary file, restoring the recorded owner, group, mode and timestamps (another user's ownership needs root), and renaming it over the path; without those fields the content would come back but the metadata would not.

Parallelism. Files of different sizes can never match, so size groups are independent units of work: after the walk, hand whole size groups to a pool of workers and merge their duplicate sets at the end, with no shared state while hashing. Threads cover most of it, because scandir, stat and read release the GIL while they wait on the disk and hashlib releases it while hashing large buffers; a process pool also works when hashing dominates, as long as workers receive paths, not file contents. The disk is usually the bottleneck, so cap concurrent readers per physical device: one or two on a spinning disk, where parallel reads turn sequential I/O into seeks, and more on an SSD, which reaches full speed only with many requests in flight. The walk parallelizes the same way, one worker per top-level subtree, since listing directories is mostly waiting on metadata. Across machines, run the cascade in MapReduce-style rounds: each machine walks its own disks and emits (size, path) records, a shuffle by size brings every candidate for one size to one reducer, and only sizes shared by two or more files go on to the fingerprint and hash rounds, each computed by the machine that owns the file and shuffled by the new key. A match across machines can be reported, moved or deleted but never linked, since hard links stay on one device, and confirming it byte by byte means streaming one copy over the network, so cross-machine sets usually rely on the 256-bit hash, and the byte comparison before linking or deleting runs within each machine.