Interview Questions

You are given a document having lot of words in it and .....

Software QA/Tests Interview Questions from Microsoft


(Continued from previous question...)

You are given a document having lot of words in it and .....

Question:
You are given a document having lot of words in it and many words have been used it the document more than once ... you are supposed to find each word with their occurrences in the document means its count .... assume you have been given a function char * GetNextWord() which fetches you next word from the document ....
1) propose the best data structure u will use to tackle this problem.
2) Write an algo to implement this
3) Tell the complexity



maybe an answer1:

1) trie
2) trie implementation will be available online, no need to replicate here
3) o(n)



maybe an answer2:

We can use a trie or Hash Map to achieve this .
If we use trie to find the count it takes o(k) , k being length of the word Using Hashmap we achieve 0(1) comeplexity

(Continued on next question...)

Other Interview Questions