Amazon Interview Question
Country: United States
Interview Type: In-Person
1) input name and find phone number
-- Trie structure for name (string), phone number as assocaited value.
-- Or hashtable (name as hash key), and link list as chaining (for name duplicatiion)
2) input phone number and find name
-- hash table
(phone number is unique, so use is as hash key)
The great thing about a trie is that it would provide functionality to easily facilitate partial searches, you type in the start of the persons name or phone number and you could return all leaf nodes that match that that prefix. Not sure how you could do this with a hashmap
Use trie data structure to store all phone numbers. insertion and search will take O(length of phone number). To display the numbers starting with one or more digits, then the complexity will be the O(prefix length)+O(number of children for the immediate prefix node * length of the remaining number from child nodes).
I am assuming you type in your search the contact(in this case freeninza) and it returns a phone linked to this contact. Using a Trie can help you on that and the time will be O(L) where L is the string lenght, in this case freeninza.
- marcelovox2 October 13, 2012