Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
if dictionary is implemented as the trie, this is the best solution. else if its an array of words, binary search
Storing dictionary in a Hashmap may be difficult.
1. Because of the size of the dictionary
2. What hashing function to be used for anagrams which are also a part of the 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;
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 ?
- bnm March 25, 2012