Not a code question, just a concept question...

I give you two arrays and they both contain strings. I want you to return to me an array that contains strings common to both arrays.

How would you do it?

My next post will be the best answer I could come up with in about 3 minutes on the phone to Apple.

Take both array (array1 and array2) and sort their contents alphabetically.

Now store two indices i (for array1) and j (for array2).

Start at i = 0 and iterate through j from j = 0.

When you find a value j where array2[j] is the same string as array1[i] then add that into a third array (resultArray) and increment i by 1 and continue iterating through j.

No repeat this until you reach the end of array2.

When you reach the end of array2 then resultArray will be an array of all strings that occurred in both array1 and array2.

It would probably be quicker while you're sorting alphabetically to generate an index of both tables by first letter, so you only need to iterate your search through strings where at least the first letters match. Course you could do that all the way through but I'm assuming the strings are of arbitrary length.

Or do some kind of fast checksum of each of the strings and compare those - but you'd have to test whether checksum generation & comparison was quicker than just plain string comparisons.

There's all sorts of questions I'd want to know first that'd influence my approach:

• What are the relative sizes of the arrays - is one massive relative to t'other?
• How long is each string
• What sort of number of strings are we talking about?
• Does either array contain duplicates, and if so how many duplicates?
• How similar are the strings in each set? Is there a high chance of hash collisions for any reason?

What language is it in?

If I could do it in Perl I think I'd do something like:
1. Convert array 1 to a hash.
2. Iterate through array 2 and see if it exists in the hash.

Something like:


The code above runs on my iMac in the following time:


Dict and DictRev are files that contain 173122 words. They both contain the same words but DictRev is reversed. Sorting DictRev by general numeric value (sort -g) gets a similar process time.

If I had to do it in Java, I would probably put array1 into a hash table creating hashes of each word, then iterate through array2 creating a hash and seeing if it existed i the hash table.
Not sure on the inbuilt data structures of Cocoa, so not sure on my approach using Objective-C.