316. A huge file contains millions of lines; exactly two are identical. How do you find them?
MediumSymbol tables & hashing
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).