Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Trie is good option but the problem with trie is that it wastes a lot of memory. Ternary tree can be used instead of trie.
really depends on implementation of trie. the classic trie implementation which has a slot for ever possible character in the language at each node would be wasteful of memory. if you design your trie such that each node has a pointer only for characters of strings it stores, it should be fine.
share your thoughts.
Imp thing here is it is designed for a mobile. I think best you can do apart from TRIE is store all the words in 26 files. Words starting with each unique alphabet in English each file (a-z 26 files). Inside the file you will have words with similar prefix just like in TRIE on different lines. So when user types first three letters of the word you know where exactly to search !
Ternary search tree will be a good solution. It will not use extra space like trie.
The ternary search tree contains three types of arrows. First, there are arrows that correspond to arrows in the corresponding trie. Traversing a down-arrow corresponds to “matching” the character from which the arrow starts. The left- and right- arrow are traversed when the current character does not match the desired character at the current position. We take the left-arrow if the character we are looking for is alphabetically before the character in the current node, and the right-arrow in the opposite case.
.
A
: \
B B
: :
C C
/ : :
B D D
:
A
The elements are ABCD,ABBA,BCD
suffix tree will be good option. Nodes will be allocated only when they are required.
take example of apple, application, aptitude
a
/
p
/ \
pl titude
/ \
e ication
if user type: ap then output will: aptitude, apple, application
if user type: app then output will be: apple, application
whenever there is new addition of word and that word require to break node at some level, then break it and make two or more nodes.
"Apartment" and "Applied" addition will make tree like this
a
/
_ p
/ / \
artment pl titude
/ \
e i
/ \
ed cation
I would also start with trie.
- Alex February 02, 2014Second option is the compressed trie.
Last one is hashing:
If we are talking about the real words it is hard to imagine the dictionary with the elements length more than 10 average. Also we probably don't want to store more than 10-20 suggestions for user (we can update frequency or use other idea to choose the right words) but for each prefix (or prefix hash and length) we can store a set of suggestions. Of course we store only prefixes we have in the dictionary. So in other words we use the prefix with length X as the key and words (only 10 best as values).