Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Read a word from the dictionary file.
2. Insert it into a prefix tree data structure in memory.
3. Repeat steps 1-2 until all words in the dictionary have been inserted into the prefix tree.
4. Using backtracking, search the board for words.
5. If a word is found and it contains 3 or more letters, search the prefix tree for the word.
6. If searching was *not* successful in the previous step, return from this branch of the backtracking stage. (There is no point to continue searching in this branch, nothing in the dictionary as the prefix tree says).
7. If searching was successful in step 5, continue searching by constructing more words along this branch of backtracking and stop when the leaf node has been reached in the prefix tree. (at that point there is nothing more to search).
8. Repeat steps 4-7 as long as there are more words to search in the backtracking.
do u want to read all the words from the dictionary which contains "all the possible English words" i don't think this will be efficient.
But I guess the person has already mentioned that he has a dictionary containing all the words .... so I guess we need to take the words from there itself
But I guess the person has already mentioned that he has a dictionary containing all the words .... so I guess we need to take the words from there itself
But I guess the person has already mentioned that he has a dictionary containing all the words .... so I guess we need to take the words from there itself
But I guess the person has already mentioned that he has a dictionary containing all the words .... so I guess we need to take the words from there itself
Read a word from the dictionary file.
2. Insert it into a prefix tree data structure in memory.
3. Repeat steps 1-2 until all words in the dictionary have been inserted into the prefix tree.
4. Using backtracking, search the board for words.
5. If a word is found and it contains 3 or more letters, search the prefix tree for the word.
6. If searching was *not* successful in the previous step, return from this branch of the backtracking stage. (There is no point to continue searching in this branch, nothing in the dictionary as the prefix tree says).
7. If searching was successful in step 5, continue searching by constructing more words along this branch of backtracking and stop when the leaf node has been reached in the prefix tree. (at that point there is nothing more to search).
8. Repeat steps 4-7 as long as there are more words to search in the backtracking.
Read a word from the dictionary file.
2. Insert it into a prefix tree data structure in memory.
3. Repeat steps 1-2 until all words in the dictionary have been inserted into the prefix tree.
4. Using backtracking, search the board for words.
5. If a word is found and it contains 3 or more letters, search the prefix tree for the word.
6. If searching was *not* successful in the previous step, return from this branch of the backtracking stage. (There is no point to continue searching in this branch, nothing in the dictionary as the prefix tree says).
7. If searching was successful in step 5, continue searching by constructing more words along this branch of backtracking and stop when the leaf node has been reached in the prefix tree. (at that point there is nothing more to search).
8. Repeat steps 4-7 as long as there are more words to search in the backtracking.
Read a word from the dictionary file.
2. Insert it into a prefix tree data structure in memory.
3. Repeat steps 1-2 until all words in the dictionary have been inserted into the prefix tree.
4. Using backtracking, search the board for words.
5. If a word is found and it contains 3 or more letters, search the prefix tree for the word.
6. If searching was *not* successful in the previous step, return from this branch of the backtracking stage. (There is no point to continue searching in this branch, nothing in the dictionary as the prefix tree says).
7. If searching was successful in step 5, continue searching by constructing more words along this branch of backtracking and stop when the leaf node has been reached in the prefix tree. (at that point there is nothing more to search).
8. Repeat steps 4-7 as long as there are more words to search in the backtracking.
1. Read a word from the dictionary file.
2. Insert it into a prefix tree data structure in memory.
3. Repeat steps 1-2 until all words in the dictionary have been inserted into the prefix tree.
4. Using backtracking, search the board for words.
5. If a word is found and it contains 3 or more letters, search the prefix tree for the word.
6. If searching was *not* successful in the previous step, return from this branch of the backtracking stage. (There is no point to continue searching in this branch, nothing in the dictionary as the prefix tree says).
7. If searching was successful in step 5, continue searching by constructing more words along this branch of backtracking and stop when the leaf node has been reached in the prefix tree. (at that point there is nothing more to search).
8. Repeat steps 4-7 as long as there are more words to search in the backtracking.
1. Read a word from the dictionary file.
2. Insert it into a prefix tree data structure in memory.
3. Repeat steps 1-2 until all words in the dictionary have been inserted into the prefix tree.
4. Using backtracking, search the board for words.
5. If a word is found and it contains 3 or more letters, search the prefix tree for the word.
6. If searching was *not* successful in the previous step, return from this branch of the backtracking stage. (There is no point to continue searching in this branch, nothing in the dictionary as the prefix tree says).
7. If searching was successful in step 5, continue searching by constructing more words along this branch of backtracking and stop when the leaf node has been reached in the prefix tree. (at that point there is nothing more to search).
8. Repeat steps 4-7 as long as there are more words to search in the backtracking.
1. Read a word from the dictionary file.
2. Insert it into a prefix tree data structure in memory.
3. Repeat steps 1-2 until all words in the dictionary have been inserted into the prefix tree.
4. Using backtracking, search the board for words.
5. If a word is found and it contains 3 or more letters, search the prefix tree for the word.
6. If searching was *not* successful in the previous step, return from this branch of the backtracking stage. (There is no point to continue searching in this branch, nothing in the dictionary as the prefix tree says).
7. If searching was successful in step 5, continue searching by constructing more words along this branch of backtracking and stop when the leaf node has been reached in the prefix tree. (at that point there is nothing more to search).
8. Repeat steps 4-7 as long as there are more words to search in the backtracking.
1. Read a word from the dictionary file.
2. Insert it into a prefix tree data structure in memory.
3. Repeat steps 1-2 until all words in the dictionary have been inserted into the prefix tree.
4. Using backtracking, search the board for words.
5. If a word is found and it contains 3 or more letters, search the prefix tree for the word.
6. If searching was *not* successful in the previous step, return from this branch of the backtracking stage. (There is no point to continue searching in this branch, nothing in the dictionary as the prefix tree says).
7. If searching was successful in step 5, continue searching by constructing more words along this branch of backtracking and stop when the leaf node has been reached in the prefix tree. (at that point there is nothing more to search).
8. Repeat steps 4-7 as long as there are more words to search in the backtracking.
1. Read a word from the dictionary file.
2. Insert it into a prefix tree data structure in memory.
3. Repeat steps 1-2 until all words in the dictionary have been inserted into the prefix tree.
4. Using backtracking, search the board for words.
5. If a word is found and it contains 3 or more letters, search the prefix tree for the word.
6. If searching was *not* successful in the previous step, return from this branch of the backtracking stage. (There is no point to continue searching in this branch, nothing in the dictionary as the prefix tree says).
7. If searching was successful in step 5, continue searching by constructing more words along this branch of backtracking and stop when the leaf node has been reached in the prefix tree. (at that point there is nothing more to search).
8. Repeat steps 4-7 as long as there are more words to search in the backtracking.
This is basically a permutation problem. Hence the total number of possible words is found by..
16p1 + 16p2 + 16p3 +................................................ + 16p15 + 16!
However this solution results in many combinations which are not possible by joining characters in the adjoining cells.
FW: find a word 's'
IW: Is a word in dictionary Trie
BS: Boggle search
v[][] = if particular cell visited earlier (0 or 1)
FW(i, j, s)
if(IW(s))
print the s and the meaning from dictionary
if(i-1 >= 0 && !v[i-1][j])
v[i-1][j] = 1
FW(i-1, j, s+a[i-1][j])
if(i+1 <= m-1 && !v[i+1][j])
v[i+1][j] = 1
FW(i+1, j, s+a[i+1][j])
if(j-1 <=0 && !v[i][j-1])
v[i][j-1] = 1
FW(i, j-1, s+a[i][j-1])
if(j+1 <= n-1 && !v[i][j+1])
v[i][j+1] = 1
FW(i, j+1, s+a[i][j+1])
BS()
for each i from 0 to m-1
for each j from 0 to n-1
v[i][j] = {0}
FW(i,j, a[i][j])
@original poster ...can you please elaborate ..what is meant by "connecting the neighboring cells." ??? say for a 2X2 matrix
a m o k
c t l p
i s w q
d k s p ......can we use "a c t m " from the upper left corner as a word ?? ,,can a rearrange these letters like "c a t m " ?? or is the order determined by D[0][0] D[0][1] D[1][0] D[1][1] ????
@original poster ...can you please elaborate ..what is meant by "connecting the neighboring cells." ??? say for a 2X2 matrix
a m o k
c t l p
i s w q
d k s p ......can we use "a c t m " from the upper left corner as a word ?? ,,can a rearrange these letters like "c a t m " ?? or is the order determined by D[0][0] D[0][1] D[1][0] D[1][1] ????
I am trying to use recursion starting with each letter in the matrix and building all the words through their neighbors until the word length doesn't go beyond the threshold (that is the longest word in the dictionary)
void allwords(char ar[][],vector<string> dic, int thresh)
{
vector<string> list
for(int row=0;row<3;row++)
for(int col=0;col<3;col++)
findWords(ar[][],row,col,ar[row][col],list,thresh,dic);
// remove duplicates fromt the list if any
sort(list.begin(),list.end());
list.erase(unique(list.being(),list.end()),list.end());
}
findWords(char ar[][],int row,int col,string word,vector<string> list,int thresh, vector<string> dic)
{
if(word.length>thresh)
return;
word=word+ar[row][col];
vector<string>::iterator it;
it= find(dic.begin(),dic.end(),word);
if(*it!=dic.end())
list.push_back(word);
// Find all possibilties with the top neighbor
if(row>0)
findWords(ar,row-1,col,word,list,thresh,dic);
if(col<3)
findWords(ar,row,col+1,word,list,thresh,dic);
if(row<3)
findWords(ar,row+1,col,word,list,thresh,dic);
if(col>0)
findWords(ar,row,col-1,word,list,thresh,dic);
// If diagonal nieghbors too has to be included
// Diagonally top right
if(row>0 &&col<3)
findWords(ar,row-1,col+1,word,list,thresh,dic);
if(row<3 && col<3)
findWords(ar,row+1,col+1,word,list,thresh,dic);
if(row>0 && col>0)
findWords(ar,row-1,col-1,word,list,thresh,dic);
if(row<3 && col>0)
findWords(ar,row+1,col-1,word,list,thresh,dic);
}
please mail me if you there's anything wrong in this method c.operatingsystems@gmail.com
int visit[N][N];
set<string> ans;
dfs(int x, int y, string& prefix)
{
if (x < 0 || y > 0 || x == N || y == N) return ;
visit[x][y] = 1; prefix.push_back(a[x][y]);
if (dict.contains(prefix)) ans.push_back(prefix);
for (int i=0; i < 8; i++)
dfs(x+X[i], y+Y[i], prefix);
prefix.pop_back();
}
for (int i=0; i < n; i++)
for (int j=0; j < n; j++)
dfs(i, j, string("")) ; // start the root
// sorry, some minor bugs fixed
int visit[N][N];
set<string> ans;
// possible movies, all up, down, left, right, and diagonals allowed
const int X[] = {-1, 1, -1, 1, 0, 1, -1, 0 };
const int Y[] = {-1, 1, 1, -1, 1, 0, 0, -1 };
void dfs(int x, int y, string& prefix)
{
if (x < 0 || y > 0 || x == N || y == N) return ;
visit[x][y] = 1; prefix.push_back(a[x][y]);
if (dict.contains(prefix))
ans.push_back(prefix);
for (int i=0; i < 8; i++)
dfs(x+X[i], y+Y[i], prefix);
visit[x][y] = 0;
prefix.pop_back();
}
// inside main
for (int i=0; i < n; i++)
for (int j=0; j < n; j++)
dfs(i, j, string("")) ; // start the root
int visit[N][N];
set<string> ans;
// possible movies, all up, down, left, right, and diagonals allowed
const int X[] = {-1, 1, -1, 1, 0, 1, -1, 0 };
const int Y[] = {-1, 1, 1, -1, 1, 0, 0, -1 };
void dfs(int x, int y, string& prefix)
{
if (x < 0 || y > 0 || x == N || y == N || visit[x][y]) return ;
visit[x][y] = 1; prefix.push_back(a[x][y]);
if (dict.contains(prefix))
ans.push_back(prefix);
for (int i=0; i < 8; i++)
dfs(x+X[i], y+Y[i], prefix);
visit[x][y] = 0;
prefix.pop_back();
}
// inside main
for (int i=0; i < n; i++)
for (int j=0; j < n; j++)
dfs(i, j, string("")) ; // start the root
- dumbhead April 03, 2012