# (Amazon Interview Q) You have more than 3 million entries of phone numbers. You have to create a phone book just like the one we have on the new phones these days. You type the name, and the numbers that match the letters you typed shows up on your phone.
For e.g: When you type 'K' all numbers under K appear,then you say "i"...all numbers under "Ki" appear..so on and so forth.How will you design/architecture this type of search? Discuss data structures you would use whats the worst case for your design?
==>
Choice 1:
TRIE is the best option to implement a cell phone contact lists, though they consume a lot of memory...
Choice 2: Directed acyclic word graph would be more efficient in terms of memory.http://en.wikipedia.org/wiki/Directed_acyclic_word_graph
Notes: Trie works like focusing on the surfix, while DAWG attend to deal with both, that's why there is acylick exist, and there are multiple path to reach an end node. As indicated in the wiki page, because of this multiple pathes, when storing attribute which correspond to the "path", i,e, store the value of path, it would be better to use the trie.
For e.g: When you type 'K' all numbers under K appear,then you say "i"...all numbers under "Ki" appear..so on and so forth.How will you design/architecture this type of search? Discuss data structures you would use whats the worst case for your design?
==>
Choice 1:
TRIE is the best option to implement a cell phone contact lists, though they consume a lot of memory...
Choice 2: Directed acyclic word graph would be more efficient in terms of memory.http://en.wikipedia.org/wiki/Directed_acyclic_word_graph
Notes: Trie works like focusing on the surfix, while DAWG attend to deal with both, that's why there is acylick exist, and there are multiple path to reach an end node. As indicated in the wiki page, because of this multiple pathes, when storing attribute which correspond to the "path", i,e, store the value of path, it would be better to use the trie.
--
♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥
No comments:
Post a Comment