Amazon Interview Question SDE-2s
Country: India
Interview Type: In-Person
problem wont describe it needs search on phone numbers as well.
By the trie would be solution when each word in contact stored separately OR use sorted array of words in each contacts.
If you need to search on phone number as well then nothing worry, use numbers in same data structure you are using. In this case, you will have all words of all contact + numbers as index.
with trie the following result will not be obtained
typing 'ama' wll give
Aman
Amazon
Neha Aman
Yes trie is the data structure for Name (First name, and last name). and It will required one HashTable for number for fast searching.
1. Trie will contain two node - one for First name, and one for Last Name. To provide search based on both - first and last name.
2. Each trie node will contain phone number to fetch contact details(Name, address etc) from HashTable
I am considering only 26 Captal letters and 26 small letters for name, so number of keys in a trie will be 52.
Time Complexity - O(logL base 52), where L = length key (first name or last name)
Disadvantage:
Trie is unbeatable in terms of time, but it is space monster. So we can use Ternary Search Tree (Each node can have maximun 3 children) in place of Trie
Time Complexity - O(logL base 3), where L = length key (first name or last name)
If you want to provide prefix based search capability in number too, than use one more trie for number in place of HashMap.
how about a trie, in which the leaf node pointed to a hash_index in a hash map of phone numbers.
This way you can search names efficiently by using the trie. And also, be able to search for phone numbers easily by directly using the hash map.
The solution should be extendable.
I would use Trie that stores everything, not only names.
The contact can be stored in a normal object. Some properties should be marked as "indexed" like name, phone number, company, and others "unindexed".
The Trie should then store more than just the name:
- First name
- Last name
- First + last
- Last + first
- Phone number
- Company
- Location
etc.
Leaves are pointers to the contact object. The Trie should be updated when contacts are added/modified/deleted.
Store each word and number in compressed tries or ternary search. No matter It is first name or last name. It is just word. At the lead node (ideally word) have reference to HashMap <Key, ContactDetails> ... By doing this, It is possible to fetch all the details of personal. Phone number, Name, email etc.. As List is already in memory so, there will not be any additional space for pointing refereces. T(n) - word length.
to find matches based on prefix, we can use a binary tree. It would be self-balancing, for example a red-black tree, so all operations inseer/modifiy/delete/find will be O(n).
Use 1 trie per search vector (first name, last name, phone number). Each trie will have some height (not to exceed the longest name/phone number).
Attach the data leaves (the actual data we are looking for) to the phone number trie (most looks ups will probably come during in-coming calls). Make the leaves for the first name trie the roots of the last name trie. Make the leaves of the last name trie the roots of the phone number trie. This results in a large trie which is logically "first name"->"last name"->"phone number" of height h.
During look up, for the first character you will need to perform h look-ups into each level the final trie, since we could be searching in the middle of a name, and maintain a list of some sort (which to get the set of names for a given letter will result in O(h) look-ups assuming you want real-time update of the possible list while typing). For each additional letter, you will prune that list.
Some optimizations are to maintain points/references from each level of the trie to all leaves below it. This will allow for faster pruning and data look-ups since you don't have to traverse the entire tree to get the to the leaf nodes. A similar tactic can be used with parent pointers in leaves too all nodes in the path to the leaf to make for quicker deletion
Can we store all the suffixes of the strings in a trie ? In this way we can search efficiently .
Below data structure would require only o(1) time to search/add/delete. We are building hash table of prefix and suffix of string and are going to store index of actual string along with value below is sample structure
[0]Aman
[1]Amazon
[2]Neha Aman
--
1 ] Aman[0]
aman
man
an
n
a
am
ama
2] Amazon[1]
amazon
mazon
azon
zon
on
n
a
am
ama
amaz
amazo
3] Neha Aman[2]
neha
eha
ha
a
neh
ne
n
aman
man
an
n
a
am
ama
HashTable===>
[key01]-->[aman]
--> 0
[key02]-->[man]
--> 0
[key03]-->[an]
--> 0->2
[key04]-->[n]
--> 0->1->2
[key05]-->[a]
--> 0->1->2
[key06]-->[am]
--> 0->1->2
[key07]-->[ama]
--> 0->1->2
[key11]-->[amazon]
--> 1
[key12]-->[mazon]
--> 1
[key13]-->[zon]
--> 1
[key14]-->[on]
--> 1
[key15]-->[amaz]
--> 1
[key16]-->[amazo]
--> 1
[key21]-->[neha]
--> 2
[key22]-->[eha]
--> 2
[key23]-->[ha]
--> 2
[key24]-->[neh]
--> 2
[key25]-->[ne]
--> 2
[key26]-->[aman]
--> 2
[key27]-->[man]
--> 2
partial string match, I would choose trie
insert: add first name, last name to construct the trie
search: whenever user inputs a letter, traverse the trie and return the subtree; prone the tree when get one input; show the results from the tree using dfs
delete: find the path, remove the label
modify: delete & insert
We can use Trie data structure
- Abi August 21, 2014