Implement file deduplication at scale

Q: Implement file deduplication at scale

This question evaluates a candidate's competence in designing and implementing scalable file deduplication systems, covering algorithmic hashing strategies, efficient disk I/O and batching, parallelization across cores or machines, large-file chunking, and safe filesystem operations like hard-linking.

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

Write a program to deduplicate files in a very large directory tree. Identify groups of identical files without loading entire files into memory. Outline your approach to hashing (e.g., size filter, partial hash, full hash), chunking for very large files, and handling hash collisions. Support a mode that replaces duplicates with hard links (when safe) and a dry-run report of duplicate sets. Explain time and space complexity, how you batch disk I/O, and how you would parallelize across CPU cores or machines.

PracHub · Accepted Answer

def solution(files, mode): import hashlib from collections import defaultdict if mode not in ('report', 'link'): raise ValueError("mode must be 'report' or 'link'") PREVIEW = 16 def content_size(chunks): total = 0 for chunk in chunks: total += len(chunk) return total def first_k(chunks, k): parts = [] remaining = k for chunk in chunks: if remaining == 0: break if not chunk: continue piece = chunk[:remaining] parts.append(piece) remaining -= len(piece) return ''.join(parts) def last_k(chunks, k): parts = [] remaining = k for chunk in reversed(chunks): if remaining == 0: break if not chunk: continue if len(chunk) <= remaining: parts.append(chunk) remaining -= len(chunk) else: parts.append(chunk[-remaining:]) remaining = 0 return ''.join(reversed(parts)) def full_digest(chunks): h = hashlib.blake2b(digest_size=32) for chunk in chunks: if chunk: h.update(chunk.encode('utf-8')) return h.hexdigest() def same_content(chunks_a, chunks_b): ia = ib = 0 oa = ob = 0 while True: while ia < len(chunks_a) and oa >= len(chunks_a[ia]): ia += 1 oa = 0 while ib < len(chunks_b) and ob >= len(chunks_b[ib]): ib += 1 ob = 0 if ia == len(chunks_a) or ib == len(chunks_b): break a = chunks_a[ia] b = chunks_b[ib] take = min(len(a) - oa, len(b) - ob) if a[oa:oa + take] != b[ob:ob + take]: return False oa += take ob += take while ia < len(chunks_a) and oa >= len(chunks_a[ia]): ia += 1 oa = 0 while ib < len(chunks_b) and ob >= len(chunks_b[ib]): ib += 1 ob = 0 return ia == len(chunks_a) and ib == len(chunks_b) records = [] for path, device_id, inode_id, chunks in files: records.append({ 'path': path, 'device': device_id, 'inode': inode_id, 'chunks': chunks, 'size': content_size(chunks) }) size_groups = defaultdict(list) for record in records: size_groups[record['size']].append(record) verified_groups = [] for group in size_groups.values(): if len(group) < 2: continue partial_groups = defaultdict(list) for record in group: key = ( record['size'], first_k(record['chunks'], PREVIEW), last_k(record['chunks'], PREVIEW) ) partial_groups[key].append(record) for partial_group in partial_groups.values(): if len(partial_group) < 2: continue digest_groups = defaultdict(list) for record in partial_group: digest_groups[full_digest(record['chunks'])].append(record) for digest_group in digest_groups.values(): if len(digest_group) < 2: continue collision_safe_groups = [] for record in digest_group: placed = False for bucket in collision_safe_groups: if same_content(record['chunks'], bucket[0]['chunks']): bucket.append(record) placed = True break if not placed: collision_safe_groups.append([record]) for bucket in collision_safe_groups:

Quick Overview

Solution

Hints

Quick Overview