Implement file deduplication at scale

Quick Overview

This question evaluates a candidate's competence in designing and implementing scalable file deduplication systems, covering algorithmic hashing strategies, efficient disk I/O and batching, parallelization across cores or machines, large-file chunking, and safe filesystem operations like hard-linking.

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: This question evaluates a candidate's competence in designing and implementing scalable file deduplication systems, covering algorithmic hashing strategies, efficient disk I/O and batching, parallelization across cores or machines, large-file chunking, and safe filesystem operations like hard-linking.

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')])`.

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

Use increasingly expensive filters: size, then a small content-based prefix/suffix fingerprint, then a full streaming hash.
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.

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.