Microsoft Interview Question
Software Engineer / DevelopersVery Easy..
Build a Patricia tree with all workds in the dictionary..
When user presses 'r' the tree is travesed from root to the node that has workds starting with 'r'...
Following that when the user presses 'a'
narrow down to look for a node in subtree that has words with 2nd letter as 'a'.... Or a Chaild node a...
Sample Dictionary Tree will be as:
Root
|
----------------------------------
| | | | | | | |
a b c d e f ...... z
| | | | | | .......|
--------- ------------
|......| |..........|
a.......z a...........z
|
-------
|......|
a......z
So the word ape will be traced as a-level1 then p-level2 and e in level 3...
Time to seach is O(logn)
Ridiculous !!! the interviewer actually mentioned the microsoft-forbidden "G" word !!!!
- Vel November 03, 2007