0

Find duplicate files by content

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Find duplicate files by content

Companies: Anthropic

Difficulty: Medium

Problem statement

You are given read access to a file system rooted at "/". Find every group of files whose contents are byte-for-byte identical. File names, extensions, and directories do not matter. Only the bytes count.

You can reach the file system only through this interface:

class FileSystem(Protocol):
    def list_dir(self, path: str) -> list[str]: ...  # names of the children of a directory
    def is_dir(self, path: str) -> bool: ...
    def size(self, path: str) -> int: ...            # size in bytes, from metadata (no read)
    def open(self, path: str) -> BinaryIO: ...       # binary stream; read(n) returns up to n bytes

Implement:

def find_duplicates(fs: FileSystem, root: str = "/") -> list[list[str]]

Return one list of absolute paths for each set of two or more identical files. Never return a file that has no duplicate. The order of groups and the order of paths inside a group do not matter.

Constraints

  • The tree can hold millions of files and can be very deep.
  • A single file can be many gigabytes, so you cannot load a whole file into memory.
  • Reading content is the expensive part. Read as few bytes as you can.
  • Empty files count as files. All empty files are duplicates of each other.

Example 1

/notes/todo.txt      "buy milk"
/backup/todo-old.txt "buy milk"
/backup/plan.txt     "buy mill"
/readme              "hi"

Output: [["/notes/todo.txt", "/backup/todo-old.txt"]]. plan.txt has the same size but different bytes, and readme has a size no other file has.

Example 2

/a/x.log  (empty)
/b/y.log  (empty)
/c/z.bin  0x00 0x01

Output: [["/a/x.log", "/b/y.log"]].

Be ready to discuss which parts are I/O-bound or CPU-bound, how you pick chunk sizes and hash functions, and how your approach scales to very large trees.

Approach

Two files are duplicates only if every byte matches, so path and name are irrelevant. The cost to avoid is reading file content: on a large tree almost all of the time goes to I/O. The plan is to reject non-duplicates with the cheapest available evidence first, and to read full content only for files that are still candidates.

Brute force. Read every file in full and group by content (or by a full-content hash). This is correct, but it reads every byte of every file, including the many files that have a unique size and so cannot have a duplicate. Comparing every pair byte by byte is worse still: O(n²) comparisons.

Staged filtering (the expected answer).

  1. Walk the tree with an explicit stack instead of recursion, so a very deep directory chain cannot overflow the call stack. Emit file paths only.
  2. Group by size. Size is metadata and costs no content reads. Files with different sizes can never be equal. Drop every group of one. In real file systems this alone removes most files.
  3. Group by a hash of the first few KB. Many files of the same size differ near the start (headers, timestamps). Hashing 4 KB per candidate is cheap. Drop groups of one.
  4. Group by a full streamed hash. For files still together, hash the whole content in fixed-size chunks (64 KB), so memory stays O(chunk) no matter how large a file is. A file no longer than the head size is already fully hashed in step 3, so skip it here.
  5. Optional byte-for-byte verification. Equal SHA-256 digests make a collision astronomically unlikely, but if the interviewer wants a proof of equality, compare streams chunk by chunk within each hash group and split it into true equality classes.

Invariants. After every stage, each group holds files that agree on every key used so far, so every pair of true duplicates is still in one group. Groups of size one are dropped as soon as they appear, because a file alone in a group cannot be part of a duplicate set. A stage reads content only for files that survived all earlier stages.

The file system is reached only through a small interface (list_dir, is_dir, size, open returning a binary stream), which matches the "content only as a stream" constraint. MemoryFS is a test double.

Code

from __future__ import annotations

import hashlib
import io
from collections import defaultdict
from typing import BinaryIO, Callable, Iterator, Protocol

CHUNK = 64 * 1024      # streaming read size
HEAD = 4 * 1024        # bytes hashed in the cheap pre-filter


class FileSystem(Protocol):
    def list_dir(self, path: str) -> list[str]: ...   # child names
    def is_dir(self, path: str) -> bool: ...
    def size(self, path: str) -> int: ...
    def open(self, path: str) -> BinaryIO: ...


def walk_files(fs: FileSystem, root: str = "/") -> Iterator[str]:
    """Iterative DFS so deep trees cannot overflow the call stack."""
    stack = [root]
    while stack:
        path = stack.pop()
        for name in fs.list_dir(path):
            child = path.rstrip("/") + "/" + name
            if fs.is_dir(child):
                stack.append(child)
            else:
                yield child


def _digest(fs: FileSystem, path: str, limit: int | None) -> bytes:
    h = hashlib.sha256()
    remaining = limit
    with fs.open(path) as f:
        while remaining is None or remaining > 0:
            want = CHUNK if remaining is None else min(CHUNK, remaining)
            block = f.read(want)
            if not block:
                break
            h.update(block)
            if remaining is not None:
                remaining -= len(block)
    return h.digest()


def _same_bytes(fs: FileSystem, a: str, b: str) -> bool:
    with fs.open(a) as fa, fs.open(b) as fb:
        while True:
            x, y = fa.read(CHUNK), fb.read(CHUNK)
            if x != y:
                return False
            if not x:
                return True


def _refine(groups: list[list[str]], key: Callable[[str], bytes]) -> list[list[str]]:
    out: list[list[str]] = []
    for group in groups:
        buckets: dict[bytes, list[str]] = defaultdict(list)
        for path in group:
            buckets[key(path)].append(path)
        out.extend(g for g in buckets.values() if len(g) > 1)
    return out


def _verify(fs: FileSystem, group: list[str]) -> list[list[str]]:
    """Split a same-hash group into true byte-identical classes."""
    classes: list[list[str]] = []
    for path in group:
        for cls in classes:
            if _same_bytes(fs, cls[0], path):
                cls.append(path)
                break
        else:
            classes.append([path])
    return [c for c in classes if len(c) > 1]


def find_duplicates(fs: FileSystem, root: str = "/", verify: bool = True) -> list[list[str]]:
    # Stage 1: size (metadata only, no reads).
    by_size: dict[int, list[str]] = defaultdict(list)
    for path in walk_files(fs, root):
        by_size[fs.size(path)].append(path)
    groups = [g for g in by_size.values() if len(g) > 1]
    # Stage 2: hash of the first HEAD bytes.
    groups = _refine(groups, lambda p: _digest(fs, p, HEAD))
    # Stage 3: full streamed hash; a file no longer than HEAD is already fully hashed.
    small = [g for g in groups if fs.size(g[0]) <= HEAD]
    large = [g for g in groups if fs.size(g[0]) > HEAD]
    groups = small + _refine(large, lambda p: _digest(fs, p, None))
    # Stage 4: optional byte-for-byte check against hash collisions.
    if verify:
        groups = [c for g in groups for c in _verify(fs, g)]
    return [sorted(g) for g in groups]


class MemoryFS:
    """In-memory FileSystem for tests: dict maps absolute paths to bytes."""

    def __init__(self, files: dict[str, bytes]) -> None:
        self.files = files
        self.dirs: dict[str, set[str]] = defaultdict(set)
        self.dirs["/"]
        for path in files:
            parts = path.strip("/").split("/")
            for i in range(len(parts)):
                parent = "/" + "/".join(parts[:i])
                self.dirs[parent].add(parts[i])

    def list_dir(self, path: str) -> list[str]:
        return sorted(self.dirs.get(path, ()))

    def is_dir(self, path: str) -> bool:
        return path in self.dirs

    def size(self, path: str) -> int:
        return len(self.files[path])

    def open(self, path: str) -> BinaryIO:
        return io.BytesIO(self.files[path])

Complexity

Let N be the number of files, D the number of directories, and B the total bytes of files that survive to the full-hash stage.

  • Walk: O(N + D) time. The stack is O(D) in the worst case. The size map holds O(N) paths.
  • Size grouping: O(N) time, no content reads.
  • Head hash: O(k · 4 KB) reads, where k is the number of files in size groups of two or more.
  • Full hash: O(B) reads and O(chunk) memory per open file. Each byte is read once.
  • Verification: for a hash group of size m that splits into c classes, O(m · c · file size). With a good hash, c is 1 and this is one extra pass over each file. Without collisions it costs O(B) more reads, which is why it is optional.
  • Overall: O(N + D) metadata work, plus content reads that are limited to real candidates. Extra memory is O(N) for paths and digests, plus O(chunk) buffers.

Test cases

  • Three files "hello" at /a.txt, /docs/b.txt, /docs/deep/c.bin → one group with all three (different names and depths do not matter).
  • /d.txt = "world", which has the same size as "hello" but different content → not in any group (removed by the head hash).
  • Two empty files /e.txt, /f/empty → [["/e.txt", "/f/empty"]] (equal size 0, equal empty hash).
  • /g1 = 10000×"x" + "A", /g2 = 10000×"x" + "B", /g3 = 10000×"x" + "A" → [["/g1", "/g3"]]. All three share the size and the first 4 KB, so only the full hash separates them.
  • One file with a unique size → never read at all.
  • Empty file system → [].
  • Two files with the same size and different bytes → [].
  • A directory chain 3,000 levels deep with a file at the bottom, matching a file at the root → one group of two, and no recursion-depth error.

Follow-ups

  • Millions of files, or a tree that does not fit in memory. Stream (size, path) records to disk and sort externally, or shard by size range across workers. Each later stage only needs one size bucket in memory at a time. Store digests, not content.
  • Parallelism. The work is I/O-bound, so use a thread pool (or async I/O) for the hashing stages, with a limit on concurrent opens to stay under the file-descriptor limit. On a distributed store, map by size bucket and reduce by hash. Answer the I/O-bound vs. CPU-bound question with numbers: SHA-256 runs at roughly 1 GB/s per core, so on spinning disks and network storage the reads dominate.
  • Chunk size and hash choice. Use 64 KB to 1 MB reads to amortize syscalls. Use a cryptographic hash (SHA-256, BLAKE2/3) when collisions must not happen without verification. Use a fast non-cryptographic hash (xxHash) for the pre-filter, followed by verification. For very large files, sample a few blocks (start, middle, end) before the full hash.
  • Real file-system details. Skip symlinks or record visited (device, inode) pairs to avoid cycles. Report hard links (same inode) as one file, not as duplicates. Handle files that change or disappear during the scan (stat again before reporting, catch permission errors). Skip special files.
  • Incremental runs. Cache (path, size, mtime) → digest so a rescan hashes only new or changed files. If the system then deletes or hard-links duplicates, verify the bytes first and act atomically.

Interviewer expectations

Mid-level (L4)

  • Walks the tree, hashes file content in chunks, and groups paths by digest.
  • Uses size grouping as the first filter once prompted, and explains why it is free.
  • Writes working code and tests empty files and files that are alone in a group.

Senior (L5)

  • Proposes the size → partial hash → full hash pipeline without prompting and states the invariant that each stage only splits groups.
  • Streams fixed-size chunks so memory does not grow with file size. Uses an iterative walk.
  • Discusses hash collisions and when to add a byte-for-byte check. Gives the cost of each stage in bytes read.

Staff (L6+)

  • Reasons about I/O vs. CPU with concrete throughput figures, chooses the chunk size and hash with those figures, and designs bounded parallel I/O.
  • Scales beyond one machine or beyond memory (external sort, sharding by size, map-reduce) and supports incremental rescans.
  • Covers real file-system cases: symlink cycles, hard links, files that change during the scan, permissions, and safe deletion of duplicates.

Sign in to comment, vote or remix.