CareerCup

we can use trie for it time and complexity in worst case would be O(m) where m = sum of number of letters in all words in the list....btw where u had written test for MS in banglore or hyderabad ?

store dictionary in hash map. for the words check if key exists. complexity is linear

for each word in the given list , do the binary search in the dictionary .if present then print it else leave it .. time complexity O(klogn)

hii...can u share the interview details plz...

Hi .. can u share interview details.. was it for IDC?? and in which city??...plz share

Complexity depends on the way the dictionary is available. So if the question needs complexity, we need to know this or make some assumptions.

How would store whole dictionary???..

We can take it up as 2 steps process:
 Step 1 : Find all constituent words . (start, end). O(n^3 ) solution
 Step 2 :  Find a subset of constituent words (s1,e1), (s2,e2) ... (sn, en), such that 
                  s1 = 0, en = N and  si - e(i-1)  = 1
          Need help here.

Sample Code

Assume the dictionary is given as a Trie.
Assume words are all in lowercase, both in dictionary and as well as word.
Example word : hellboy == ( hell, boy) OR hellboy (assuming this to be a word)
constitutent words : (he,0,1) , (hell,0,3), (boy,4,6), (hellboy,0,6)
Aim : To find all constitutent words;
Approach :
   Start search gram wise 
   all 1-grams, all 2-grams, all 3-grams, all 4-grams, all 5-grams.
   DO A BFS 
   

Search Time :
1 gram : n   : 1 *n    = 1*n - 1 * 0
2 gram : n-1 : 2 (n-1) = 2n - 2 * 1
3 gram : n-2 : 3 (n-2) = 3n - 3 * 2 
4 gram : n-4 : 4 (n-3) = 4n - 4 * 3 
n gram : 1    :n  1    = n*n - n * (n -1 ) 
Total Complexity : n (1 + 2 + 3+ ... + n ) -  sum [ i (i-1)]  where i =0 .. n 
				= n * n (n+1)/ 2 -   (1^2 + 2^ 2 + 3^2 ... n^2 ) + ( 1+2 + 3 + ... +n )
				= O(n^3)

ListOfFoundWords :  (start, end, len)

Define a search				
SearchQueue : (start, end, len)
(0,1), (1,1), (2,1), (3,1), .. (n-1, 1)

Can I resume search in trie ? Nopes. Each search is going to be fresh . search a key of length k is O(k) operation in trie. But so is calculating Hash 

for ngramLength = 1;

for i  : 0 to word.length - 1;
  enqueue (i, ngramlength)

while( Queue not empty) 
    (start, len) = dequeue 
	 result = find (word, start, len ) in dictionary 
	 IF PATHFOUND  
		enqueue (start , len + 1)
	 ELSE IF WORDFOUND
		add to ListOfFoundWords
	 ELSE 
	     CONTINUE;