Read into a list, sort. For two loops, iterate and advance each index as appropriate. The problem itself is not that hard but what makes it difficult for me was trying to do it on the white board. My advice: have some practice run yourself on a white board with some of the fundamental algo questions: the kinds that will find in CS 101 mid-term.

Better still to read the first into a HashMap and then as you read the second list look it up in the HashMap. If you find the entry in the HashMap put it into a List containing the intersections. For any reasonable hashing function that would be O(n) for the whole operation. Of coure, since we're talking about reading from disk files it will all probably be I/O bound.

The best soln imo is to use a trie. So put the list of first words into a trie. And then go through the list of second words and check if they are in the trie. Would be order of n , for inserting and checking , where n is length of the word. Memory can ,in worst case can be 26 power n, assuming english alphabet.

Cmcr

This problem is the textbook example for a bloom filter (because of large data and likelihood of disk access). This is probably the insight they were hoping for, but they probably would have settled for using a common hash set as well.