Count the occurance of all the words in a document. You are given a method char * GetNextWord() that returns the next word in the document. - What is the best datastructure to suit this requirement- Write a algorith to do the same- What is the order of the algorithm

Interview Candidate
Oct 12th, 2006
7
1528

Showing Answers 1 - 7 of 7 Answers

Sivaswami Jeganathan

Oct 31st, 2006

This concept is like Single Linked List.LinkedList : the next data can be got through linkHere : the next word can be got through the function.There can be no backtracking also.So the best search method is Linear search used in Single Linked List.Thanks,Shiva.

sumit

Nov 15th, 2006

use BST to store the words along with their count . insertion and search will have a complexiety of O(log n)

csk varma

Dec 28th, 2006

actually its optimal to use hashing on the words.......we can use a hash table to store the frequencies of words....and as search, inserion , updation time complexity in hasing is O (1)....and assuming there re n words.the net complexity is O(n)...........if we use BST , we will get O(n lg n) coz for each of the n words sacnned, we need to search in the bst and update which takes O(lg n) time ..hence net complexity is O(n lg n)