File Deduplication and Content Hashing

What's being tested

Candidates must show practical mastery of hashing for content-identification and of cache/eviction structures (esp. LRU) under performance constraints: correctness (collision handling, determinism) plus throughput (memory layout, prefetching, vectorized ops). Interviewers probe tradeoffs between speed, memory, and correctness in real-world deduplication and memoization.

Patterns & templates

• Open addressing (linear/quadratic probing) — highest locality; target load factor < 0.7 to keep probe length short and O(1) average lookup.

• Separate chaining — use when keys are large or variable; avoid pointer-heavy lists by using contiguous buckets (vector of vectors).

• Canonical/deterministic hashing — canonicalize args (sorted keys, stable serialization) then hash with SHA-256 or BLAKE2 to get fixed-length digests for persistence and cross-process equality.

• Collision strategy — never treat hash equality as proof; store and compare a small content fingerprint plus either full content or a second hash for safety.

• Cache-efficient layout — favor contiguous arrays, 64-byte alignment, and prefetching; batch-hash multiple items to exploit CPU vectorization and reduce branch mispredictions.

• LRU skeleton — combine a hashmap + doubly-linked list for O(1) insert/get/evict; on-disk persistence via atomic snapshots or append-only WAL.

• Bulk dedupe — two-pass: cheap fingerprint (e.g., rolling hash) to group candidates, then byte-for-byte or cryptographic-hash verification.

Common pitfalls

Pitfall: Treating a cryptographic hash as collision-proof — always design a verification step for rare collisions or use a 2-stage fingerprint+full-compare.

Pitfall: Optimizing for hash CPU only — forgetting memory bandwidth and cache misses will kill real throughput; measure p99 lookups, not just cycles.

Pitfall: Non-deterministic key serialization — using unordered maps or non-stable encoders causes cache misses and incorrect persistence semantics.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.