How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Anthropic.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Anthropic during technical interviews.

Detect duplicate files efficiently | Anthropic Coding Question

Quick Overview

This question evaluates understanding of scalable file-deduplication and system-design concepts, including content hashing, I/O minimization, hash-collision handling, memory constraints, parallelization, incremental updates, and cross-machine deduplication.

Detect duplicate files efficiently

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given access to a very large file system containing file paths and read access to file contents. Design an algorithm to identify groups of files that are byte-identical (true duplicates) across all directories. Return groups of file paths where each group contains duplicates. Discuss an approach that filters by size first, then uses partial hashing, then full hashing to minimize I/O; explain how to handle hash collisions, memory constraints, and parallelization. Extend the design to support incremental updates as files are added/modified, cross-machine deduplication, and safe replacement with hard links or content-addressed storage.

Quick Answer: This question evaluates understanding of scalable file-deduplication and system-design concepts, including content hashing, I/O minimization, hash-collision handling, memory constraints, parallelization, incremental updates, and cross-machine deduplication.

Maintain an **incremental index of duplicate files** as files are added, modified, deleted, and queried, and report the current groups of byte-identical files on demand. This models the core index of a real duplicate-file detector. In practice such a pipeline filters candidates by file size, then by a partial signature from the start/end of the file, then by a full hash, and finally by exact byte comparison to rule out hash collisions. Here, file contents are already given as strings, so two files count as duplicates only when their contents are **exactly equal**. ## Function Implement: ```python def solution(operations): ``` `operations` is a list of operations to process **in order**. Each operation is a list/tuple whose first element is the operation kind. ## Operations At any moment, each **path** maps to at most one current content (paths are unique). - **`('ADD', path, content)`** — set the current content at `path` to `content`. If `path` already exists, its previous content is **replaced**. - **`('MODIFY', path, content)`** — identical behavior to `ADD`: set the current content at `path` to `content`, replacing any previous content. If `path` does not already exist, it is created. - **`('DELETE', path)`** — remove `path` and its content if it exists. If `path` does not exist, the operation has **no effect**. - **`('QUERY',)`** — report the current duplicate groups (see below). ## What a QUERY returns A **duplicate group** is a set of paths whose current contents are all exactly equal. For each `QUERY`, collect every duplicate group that contains **at least 2 paths**, and: - Sort the paths **within each group** lexicographically. - Sort the **list of groups** by each group's first (lexicographically smallest) path. Paths whose content is unique (no other path currently shares it) are **not** included. If there are no duplicate groups, the `QUERY` result is an empty list `[]`. ## Return value Return a list containing one result **per `QUERY` operation**, in the order the queries occur. Each result is itself a list of groups, and each group is a list of path strings. ## Notes - Content may be the **empty string** `""`; two empty-content files are duplicates of each other. - Equality is exact: files whose contents only partially match (e.g. share a prefix and suffix) are **not** duplicates. ## Constraints - `1 <= len(operations) <= 2 * 10^5` - `0 <= len(content) <= 10^5` for a single `ADD`/`MODIFY` operation - The sum of `len(content)` over all `ADD`/`MODIFY` operations is `<= 10^6` - `1 <= len(path) <= 200`

Constraints

1 <= len(operations) <= 2 * 10^5
0 <= len(content) <= 10^5 for a single ADD/MODIFY operation
The sum of len(content) over all ADD/MODIFY operations is <= 10^6
1 <= len(path) <= 200; ADD/MODIFY replace existing content at that path, and DELETE on a missing path has no effect

Examples

Input: ([('ADD', '/a.txt', 'hello'), ('ADD', '/b.txt', 'world'), ('ADD', '/c.txt', 'hello'), ('QUERY',), ('MODIFY', '/b.txt', 'hello'), ('QUERY',)],)

Expected Output: [[['/a.txt', '/c.txt']], [['/a.txt', '/b.txt', '/c.txt']]]

Explanation: The first QUERY sees '/a.txt' and '/c.txt' with identical contents. After modifying '/b.txt' to 'hello', all three files are duplicates.

Input: ([('ADD', '/x/1', 'aa'), ('ADD', '/x/2', 'bb'), ('ADD', '/y/3', 'aa'), ('ADD', '/z/4', 'bb'), ('QUERY',), ('DELETE', '/x/2'), ('QUERY',)],)

Expected Output: [[['/x/1', '/y/3'], ['/x/2', '/z/4']], [['/x/1', '/y/3']]]

Explanation: Initially there are two duplicate groups: the 'aa' files and the 'bb' files. After deleting '/x/2', only the 'aa' group remains.

Input: ([('QUERY',), ('ADD', '/empty', ''), ('ADD', '/also_empty', ''), ('ADD', '/unique', 'x'), ('QUERY',), ('MODIFY', '/also_empty', 'x'), ('QUERY',)],)

Expected Output: [[], [['/also_empty', '/empty']], [['/also_empty', '/unique']]]

Explanation: The first QUERY runs on an empty index. Then two empty files become duplicates. After '/also_empty' is changed to 'x', it becomes a duplicate of '/unique' instead.

Input: ([('ADD', '/a', 'abc'), ('MODIFY', '/b', 'abc'), ('ADD', '/a', 'def'), ('DELETE', '/missing'), ('QUERY',)],)

Expected Output: [[]]

Explanation: MODIFY acts like an upsert, so '/b' is created with 'abc'. Then '/a' is replaced with 'def'. Deleting a missing path does nothing, so no duplicate group exists at QUERY time.

Input: ([('ADD', '/p1', 'abcdefgh12345678X87654321'), ('ADD', '/p2', 'abcdefghABCDEFGHX87654321'), ('ADD', '/p3', 'abcdefgh12345678X87654321'), ('QUERY',)],)

Expected Output: [[['/p1', '/p3']]]

Explanation: Files '/p1' and '/p2' have the same length and the same beginning and ending segments, so a partial-signature filter would keep them as candidates. Exact content still shows only '/p1' and '/p3' are true duplicates.

Hints

Keep a forward map from path to its current bucket so an update can remove the old version in O(1) average time before reinserting the new one.
Use a reverse index keyed by size, partial signature, full hash, and exact content. Also track which exact-content buckets currently have at least two paths so QUERY does not need to rescan every stored file.

Quick Overview