Detect duplicate files efficiently

Q: Detect duplicate files efficiently

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.

Q: 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.

Q: What difficulty level is this coding question?

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

Q: What role is this question designed for?

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

Question

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.

PracHub · Accepted Answer

def solution(operations):
    import hashlib

def make_candidate(content):
        size = len(content)
        head = content[:8]
        tail = content[-8:]
        full_hash = hashlib.sha256(content.encode('utf-8')).hexdigest()
        return (size, head, tail, full_hash)

path_meta = {}
    candidate_buckets = {}
    duplicate_ids = set()

def remove(path):
        if path not in path_meta:
            return
        cand, content = path_meta.pop(path)
        exact_map = candidate_buckets[cand]
        group = exact_map[content]
        group.remove(path)
        exact_id = (cand, content)

if len(group) >= 2:
            duplicate_ids.add(exact_id)
        else:
            duplicate_ids.discard(exact_id)

if not group:
            del exact_map[content]
            duplicate_ids.discard(exact_id)
            if not exact_map:
                del candidate_buckets[cand]

def add_or_replace(path, content):
        remove(path)
        cand = make_candidate(content)
        exact_map = candidate_buckets.setdefault(cand, {})
        group = exact_map.setdefault(content, set())
        group.add(path)
        exact_id = (cand, content)
        if len(group) >= 2:
            duplicate_ids.add(exact_id)
        path_meta[path] = (cand, content)

answers = []

for op in operations:
        kind = op[0]
        if kind == 'ADD' or kind == 'MODIFY':
            _, path, content = op
            add_or_replace(path, content)
        elif kind == 'DELETE':
            _, path = op
            remove(path)
        elif kind == 'QUERY':
            groups = []
            for cand, content in duplicate_ids:
                groups.append(sorted(candidate_buckets[cand][content]))
            groups.sort(key=lambda group: (group[0], group))
            answers.append(groups)
        else:
            raise ValueError(f'Unknown operation: {kind}')

return answers

Quick Overview

Solution

Hints

Quick Overview