Skip to interview prep
Apexed

316. A huge file contains millions of lines; exactly two are identical. How do you find them?

MediumSymbol tables & hashing

Technical
Show model answer

Comparing all pairs is hopeless at O(n²) line comparisons. Hash each line with a strong hash (for example, 64-bit or 128-bit) and store hash → byte offset in a hash map. When a hash repeats, seek to the stored offset and compare the actual lines, since different lines can share a hash; only a true match is reported. This is O(total size) expected time with O(n) memory for hashes and offsets, far less than storing the lines.

If even the hash table does not fit in memory, partition: write each line (or its hash and offset) into one of B bucket files chosen by hash, so identical lines land in the same bucket, then process each bucket in memory. Sorting the (hash, offset) pairs externally also works, at O(n log n).

A huge file contains millions of lines; exactly two are identical. How do you find them — Data structures & algorithms interview question — Apexed