Interview Question for Software Engineer at Google:

Traverse the first list. Insert all the elements in the list into a hash table. Complexity: O(n)
Traverse the second list. For each element in the list, look it up in the hash table. If it is in the hash table, then insert it into the destination list. Complexity: n * O(1) = O(n)
Total complexity: O(n)

Hi Radu Litiu,

Your solution is correct though the complexity analysis is incorrect.

Insertion and lookup from the hashtable can take a worst case performance of O(n) or O(logn) if you use a priority queue as the backend storage. This means that while traversing the lists for n times, each time you can encounter a O(n) complexity thus resulting in a worst case performance of O(n^2), or at least O(nlogn).