CareerCup

A sorted link list contains a node as a structure of int and char *, As we read the next word, we will traverse the link list if we got the exact word then it increment the int of the node otherwise we will create a node in which we will allocate a memory of word length and add it at a proper place.
Link List : Best case : 1. Wrost case : n.
BST : Best case 1, Worst case n, Average Case : logn.

A sorted link list contains a node as a structure of int and char *, As we read the next word, we will traverse the link list if we got the exact word then it increment the int of the node otherwise we will create a node in which we will allocate a memory of word length and add it at a proper place.
Link List : Best case : 1. Wrost case : n.
BST : Best case 1, Worst case n, Average Case : logn.

Hash table could be a good solution with O(1) complexity. where key would be a no. and value reflects frequency.

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.

@aalok: "With English Dictionary the complexity will be O(log n)foe each word."

Its not correct. The complexity will be linear in size of word length as with each character you traverse one none. So len(word) nodes at max.Thus complexity is O(len(word)).

i think we can use linked list for solving this problem efficiently
struct word
{
char str[20];
int count;
char flag;
};
initially flag is 'f' for all words in the document and count=0 for all whenever an word is discovered its flag is set to 't'
1.take word from document one by one using nextword()
2.if its flag is 'f' then count=1 else count=count+1;
3.keep untill we reach end of the document

why not use a map<string, int>?

why not use a map<string, int>?

duh ! Why would you even consider a linked list when you can just use a hashtable? O(1) insert, lookup and O(n) space !