Find duplicate strings in a large file

Question

A file contains a large number (eg.10 billion) of strings and you need to find duplicate Strings. You have N number of systems available. How will you find duplicates

Answer 1

Split the file into N pieces. On each machine, load as much of the piece into memory as you can, and sort the strings. Write these chunks to mass storage on that machine. On each machine, merge the chunks into a single stream, and then merge the stream from each machine into a stream that contains all of the strings in sorted order. Compare each string with the previous. If they are the same, it is a duplicate.

Answer 2

erickson's answer is probably the one expected by whoever set this question.

You could use each of the N machines as a bucket in a hashtable:

• for each string, (say string number i in sequence) compute a hash function on it, h.
• send the the values of i and h to machine number n for storage, where n = h % N.
• from each machine, retrieve a list of all hash values h for which more than one index was received, together with the list of indexes.
• check the sets of strings with equal hash values, to see whether they're actually equal.

To be honest, though, for 10 billion strings you could plausibly do this on 1 PC. The hashtable might occupy something like 80-120 GB with a 32 bit hash, depending on exact hashtable implementation. If you're looking for an efficient solution, you have to be a bit more specific what you mean by "machine", because it depends how much storage each one has, and the relative cost of network communication.