Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Linked list will insert in O(1) time but membership testing will be O(n) time. Hash table will be good for insert, delete, membership testing, but not random selection.
See below why storing the object in an ArrayList and the object's index into the array in a Hash table accomplishes all required functions in O(1) time.
Given object T which can return some unique key T.key(), maintain an Array<T> object and a HashMap<typeof(T.key())> Store the object in the array and the index of the array in the hash table at the location T.key() . This gives you random access (via array), insert, and deletion in constant O(1) time.
LinkedList is fast for insertion and deletion except random selection. In this scenario I think HashTable may be appropriate.
- RiponCoder February 21, 2014