Google
4.2 of 5 2,276 reviews
www.google.com Mountain View, CA 5000+ Employees

Google Software Engineer Interview Question

"Given two linked lists, return the intersection of the two lists: i.e. return a list containing only the elements that occur in both of the input lists."
Add Tags [?]
Answer Flag Question

Part of a Software Engineer Interview Review - one of 2,994 Google Interview Reviews

Answers & Comments

1
of 1
vote
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)
- Radu Litiu on Oct 13, 2009 Flag Response
0
of 1
vote
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).
- neakor on Nov 7, 2009 Flag Response
0
of 0
votes
Here is where I am confused: A hashtable is supposed to have a O(1) lookup, is it not?

The actual implementation of a hash table is platform specific. For e.g. C++ hashtables are Balanced binary search trees?
- vic on Nov 27, 2009 Flag Response

To comment on this question, Sign In with Facebook or Sign Up


Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Google interview questions and advice. All interview reviews posted anonymously by Google employees and interview candidates.