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.

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.

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.

Hints

  1. 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.
  2. 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.

Community answers

Answer by jayceeLOL

from collections import defaultdict from hashlib import sha256 class File: def init(self): self.paths = defaultdict() self.content = defaultdict(set) def add_file(self, path, content): if path in self.paths.keys(): self.del_file(path) data = content.encode("utf-8") hashed_data = sha256(data).hexdigest() self.paths[path] = hashed_data self.content[hashed_data].add(path) def mod_file(self, path, content): self.add_file(path, content) def del_file(self, path): data = self.paths.get(path, None) if path in self.paths: del self.paths[path] if data and data in self.content.keys() and path in self.content[data]: self.content[data].remove(path) def query(self): groups = list() for k, paths in self.content.items(): if len(paths) > 1: p = sorted(list(paths)) groups.append(p) return sorted(groups, key=lambda x: x[0]) def solution(operations): file_tree = File() res = [] for op in operations: print(op) if op[0] == "ADD": file_tree.add_file(op[1], op[2]) elif op[0] == "MODIFY": file_tree.mod_file(op[1], op[2]) elif op[0] == "DELETE": file_tree.del_file(op[1]) elif op[0] == "QUERY": res.append(file_tree.query()) return res This is essentially a file system implemented like a trie, with a reverse index for duplicate. Operations are composable, making add, modify, and delete very streamlined

Loading coding console...

Show the approach

Approach

The solution maintains an incremental duplicate index that stays correct across ADD/MODIFY/DELETE and answers each QUERY in time proportional to what it returns.

Cascade key. make_candidate(content) builds a tuple (size, head, tail, full_hash) — exactly the real-world filter chain (file size → partial signature from the first/last 8 chars → SHA-256 of the whole content). This is a cheap "probably-equal" fingerprint.

State.

  • path_meta: path → (candidate, content), so a path can be found and removed in O(1).
  • candidate_buckets: candidate → {content: set(paths)}. The inner dict keys on the full content, so two strings that share a candidate fingerprint but differ are kept in separate groups — this is what eliminates hash collisions and guarantees groups are true (byte-exact) duplicates.
  • duplicate_ids: the set of (candidate, content) keys whose path-set currently has ≥2 members.

Mutations. add_or_replace first removes any prior content at the path (so MODIFY = delete + insert), then inserts the path into the right inner group and adds the key to duplicate_ids once the group reaches size 2. remove pulls the path out and re-checks: if the group dropped below 2 (or emptied), the key is discarded from duplicate_ids and empty containers are pruned.

Query. Because duplicate_ids already holds exactly the groups with ≥2 paths, QUERY just iterates those keys, sorts each group lexicographically, and sorts the groups by their first path (the (group[0], group) key) — no scan over non-duplicate files. Correctness follows from duplicate_ids being kept in lock-step with every mutation.

Space complexity:
O(F + C), where F is the number of currently indexed files (entries in path_meta and the path sets) and C is the total stored content length (each path's content is retained as a dict key).