|
234. There is a document containing lots of information ... .....
Microsoft Interview Questions and Answers
(Continued from previous question...)
234. There is a document containing lots of information ... .....
Question:
Q) There is a document containing lots of information. You have a function char * getNextWord() which returns the next word from the document.
a) which data structure should be used for maintaining the information about the frequency of words.
b) Write an effective algo for maintaining the information about the frequency of each word in the document.
c) what is the complexity of algorithm.
maybe an answer:
Using a Trie will solve the purpose.
If the word is repeated, increase the repeat count at the leaf node. Otherwise add word in the list.
Time taken to increase repeat count will be (log n x d), where n is the length of longest word and d is the number of alphabets permitted(as per english dictionary which will be 26).
So Pseudo code can be formed as .
.
1. Read the word getNextWord();
2. Look up the Trie table
2.a. If found incremnet the repeat count of the table else goto 2.b
2.b. Add the word in the Trie
3.Goto Step 1, Until all the words are read.
With English Dictionary the complexity will be O(log n)foe each word.
(Continued on next question...)
Other Interview Questions
| 