Quick Overview

This question evaluates the ability to design scalable file deduplication algorithms, specifically testing knowledge of hashing strategies, collision handling, memory and I/O optimization, handling very large files, incremental/resumable operation, and complexity and trade-off analysis.

Find and remove duplicate files

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given a directory tree that may not fit in memory, detect and optionally remove duplicate files. Define the algorithm, including how you handle very large files, hashing strategy (e.g., size grouping, partial hash, full hash or chunked rolling hash), collision handling, memory and I/O optimization, and how you would make it incremental and resumable. Provide complexity analysis and discuss trade-offs.

Quick Answer: This question evaluates the ability to design scalable file deduplication algorithms, specifically testing knowledge of hashing strategies, collision handling, memory and I/O optimization, handling very large files, incremental/resumable operation, and complexity and trade-off analysis.

You are given a snapshot of a directory tree as a list of (path, content) pairs. Two files are duplicates if their contents are exactly equal, even if their paths are different. Write a function solution(files, remove) that simulates a scalable deduplication pipeline instead of doing O(n^2) pairwise comparisons: first group files by size, then by a cheap partial fingerprint, then by a full hash, and finally verify exact equality so hash collisions never cause wrong removals. For this coding task the file contents are already provided as strings, but the same staged design is what you would use for very large files by hashing them chunk-by-chunk and persisting metadata for incremental, resumable scans. For each duplicate group, keep the lexicographically smallest path as the canonical copy. If remove is True, return the other paths as removable. Do not mutate the input.

Constraints

  • 0 <= len(files) <= 200000
  • Each path is unique
  • 0 <= len(content) <= 100000 for each file
  • The sum of all content lengths is at most 2000000 in this coding version

Examples

Input: ([('root/a.txt', 'abc'), ('root/b.txt', 'xyz'), ('root/c.txt', 'abc'), ('root/d.txt', 'xyz'), ('root/e.txt', 'p')], True)

Expected Output: ([['root/a.txt', 'root/c.txt'], ['root/b.txt', 'root/d.txt']], ['root/c.txt', 'root/d.txt'])

Explanation: Files root/a.txt and root/c.txt match exactly, and root/b.txt and root/d.txt match exactly. root/e.txt is unique.

Input: ([('a', 'cat'), ('b', 'cat'), ('c', 'dog')], False)

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

Explanation: The duplicate group is still reported, but remove is False so no path is marked for deletion.

Hints

  1. Start by grouping files by length; files with different sizes can never be duplicates.
  2. Use a multi-stage fingerprint: cheap prefix/suffix key first, full hash next, and exact content equality last to protect against collisions.

Loading coding console...