Design file deduplication algorithm
Company: Anthropic
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design an algorithm to deduplicate files in a storage system. Compare fixed-size versus content-defined chunking and explain how you would choose hash functions (e.g., cryptographic hashes versus rolling hashes). Describe collision detection/mitigation, handling of very large files that do not fit in memory, streaming ingestion, and opportunities for parallelization and I/O optimization. Analyze time and space complexity and discuss data structures for fast lookups (e.g., hash tables, Bloom filters, LSM-based indexes).
Quick Answer: This question evaluates algorithm design and systems engineering competencies including chunking strategies, hash-function selection and collision mitigation, large-file and streaming processing, parallelization and I/O optimization, complexity analysis, and selection of lookup/index data structures such as hash tables, Bloom filters, or LSM-based indexes. Common in the Coding & Algorithms domain, it examines trade-offs between scalability, performance, and correctness under resource constraints and tests both conceptual understanding and practical application to real-world system-level constraints.
A storage system stores identical chunks only once. Real deduplication systems often use a rolling hash to choose chunk boundaries and a strong hash plus byte verification to confirm duplicates. In this problem, the boundary detector is simplified and duplicate detection is exact: two chunks are duplicates only if their full string contents are equal. Given a list of file contents, compute how many bytes must be stored under two strategies: (1) fixed-size chunking and (2) content-defined chunking (CDC). For fixed-size chunking, split each file into consecutive chunks of length fixed_size, except the last chunk which may be shorter. For CDC, scan each file from left to right and maintain a rolling sum of the ASCII codes of the last window_size characters of the current chunk. Cut a chunk after position i if the current chunk length is at least window_size and rolling_sum % divisor == target, or if the current chunk length reaches fixed_size (the maximum CDC chunk size). After a cut, start a new chunk and reset the rolling window. Any remaining suffix becomes the final chunk. Return [fixed_unique_bytes, cdc_unique_bytes]. Use a hash set for exact dedup lookup.
Constraints
- 0 <= len(files) <= 10^4
- 1 <= window_size <= fixed_size <= 10^5
- 1 <= divisor <= 10^9
- 0 <= target < divisor
- The sum of lengths of all file strings is at most 2 * 10^5
- Each file may be empty and contains ASCII characters
Examples
Input: ([], 4, 2, 5, 0)
Expected Output: [0, 0]
Explanation: There are no files, so neither strategy stores any bytes.
Input: (["abcdef", "abcdef"], 3, 2, 5, 0)
Expected Output: [6, 6]
Explanation: Fixed-size chunks are ["abc", "def"] for both files, so only 6 bytes are unique. CDC produces ["ab", "cde", "f"] for each file, again totaling 6 unique bytes.
Hints
- You do not need to store every chunk occurrence. A hash set of chunks already seen is enough to count only unique stored bytes.
- For CDC, keep the rolling sum of the last window_size characters and reset that state every time you cut a chunk.