Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
Following link gives you better understanding.
en.wikipedia.org/wiki/Trie
In leaf node you can put count(occurrences of the word).
So once you construct a trie, you can easily tell number of occurrences of word(Time Complexity for searching = size of word)
What can be more optimal than iterating over the document character only once?
I think the solution is to iterate over each word from the beginning, while adding each word to the Trie. When we try to add a word that already in, then we update the $->counter of that word to be $->counter=$->counter+1.
Note: $ is the closing character of each word on the Trie. To $ we add a field called counter that count each occurrence of that word.
As voora suggested, reading about Trie might help you understand the solution.
Use hash table with key "word" and "count" as value.
- Anonymous September 22, 2011