Amazon Interview Question
Country: India
What if you are going in one direction but a word has multiple words within it.
For example: "automobile" has "auto" in it, which is also a valid word. Auto is just a prefix of automobile though, so it will just return automobile right? Do tries handle that?? I'm not sure
I agree with the trie or prefix tree. @Lucas, yes I believe it covers that case. Imagine you are scanning one row (or column) and you have say "abcdautomobilezzz" and when you start at the second 'a' and traverse down to 'o' which makes "auto", you can use a wordCount variable in your trie to indicate this is a word. The algorithm will continue if more char matches; in this case, "mobile" matches.
can anybody tell how will you form the trie, this question has nothing to do with trie. Trie is mostly used in pattern matching, and here we need to try each and every possible combination of words and then check it against a dictionary whether that word exist in the dictionary or not. Trie is not going to help in any way. If It can help please write the code here.
Thanks
I believe the trie is mostly an optimization in the context of this question. It will only help if the 2d matrix consists of largely random characters. In the worst case, if most/all combinations of the characters in the 2d matrix are valid words, then i dont think a trie will really help.
Following is my code. The 2d matrix is converted to a set of base strings consisting of left-right rows, right-left rows, top-down columns and down-top columns. Then each base string is iterated on to verify for valid word combinations and printed.
##SETUP
mat2d = [ ['c', 'a', 't'],
['g', 'o', 'd'],
['f', 'b', 'r']]
dictx={ 'cat': 1,
'god': 1,
'go': 1,
'dog': 1,
'do': 1,
'boa':1
}
##CREATE BASE STRINGS
M = len(mat2d)
N = len(mat2d[0])
base_str_set=list()
#row by row
for i in range(M):
temp_str1=""
temp_str2=""
for j in range(N):
temp_str1 += mat2d[i][j] #left to right
temp_str2 +=mat2d[i][N-1-j] #right to left
base_str_set.append(temp_str1)
base_str_set.append(temp_str2)
#col by col
for j in range(N):
temp_str1=""
temp_str2=""
for i in range(M):
temp_str1 += mat2d[i][j] #top to bot
temp_str2 += mat2d[M-1-i][j] #bot to top
base_str_set.append(temp_str1)
base_str_set.append(temp_str2)
#ITERATE ON BASE STRINGS AND PRINT VALID WORD COMBINATIONS
for base_str in base_str_set:
for i in range(len(base_str)):
for j in range(i,len(base_str)):
if base_str[i:j+1] in dictx:
print base_str[i:j+1]
Are the words formed in the same direction throughout? if we are going from left to right on a row in the matrix, do we have to keep going right? or can we start from left to right and turn top or bottom to check for valid words?
basically, i want to clarify if this is truly a variation of the "flood fill" algorithm as another user is suggesting.
Solution with trie as dictionary
class Trie
{
public:
Trie():root(NULL){}
Node* root;
int searchInNode(Node* root, char ch)
{
if (!root)
return -1;
int size = root->next.size();
if(size==0)
return -1;
for(int i=0;i<size;i++)
{
if(root->next[i]->ch==ch)
return i;
}
return -1;
}
void push(Node* node, string &str,int pos)
{
if(pos == str.size())
{
node->end=true;
return;
}
if(!node)
return;
int i = searchInNode(node,str[pos]);
if (i>=0)
{
push(node->next[i],str,pos+1);
}
else
{
Node* newNode = new Node;
newNode->ch=str[pos];
node->next.push_back(newNode);
push(newNode,str,pos+1);
}
}
void Insert(string str)
{
if(!root)
root = new Node;
push(root,str,0);
}
bool matchNode(Node* node,string& str, int pos)
{
if(NULL == node)
return false;
if (pos == str.size())
{ if (node->end)
return true;
else
return false;
}
int i=searchInNode(node,str[pos]);
if(i>=0)
return matchNode(node->next[i],str,pos+1);
else
return false;
}
bool match(string str)
{
return matchNode(root,str,0);
}
int matchRow(Node* node,char ch[][3],int M,int N,int start)
{
if (!node)
return start;
if(start==N)
return start-1;
int i = searchInNode(node,ch[M][start]);
if(i>=0)
return matchRow(node->next[i],ch,M,N,start+1);
else
return start-1;
}
int matchCol(Node* node,char ch[][3],int M,int N,int start)
{
if (!node)
return start;
if(start==M)
return start-1;
int i = searchInNode(node,ch[start][N]);
if(i>=0)
return matchRow(node->next[i],ch,M,N,start+1);
else
return start-1;
}
void matchRow(char ch[][3],int M,int N)
{
for(int row=0;row<M;row++)
for(int col=0;col<N;col++)
{
int matlen=matchRow(root,ch,row,N,col);
for(int i=col;i<=matlen;i++)
cout<<ch[row][i];
}
}
void matchCol(char ch[][3],int M,int N)
{
for(int col=0;col<N;col++)
for(int row=0;row<M;row++)
{
int matlen=matchCol(root,ch,M,col,row);
for(int i=col;i<=matlen;i++)
cout<<ch[i][col];
}
}
};
void main ()
{
Trie trie;
trie.Insert("cat");
trie.Insert("god");
trie.Insert("go");
trie.Insert("dog");
trie.Insert("do");
trie.Insert("boa");
char arr[3][3]={'c','a','t','g','o','d','f','b','r'};
trie.matchRow(arr,3,3);
trie.matchCol(arr,3,3);
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 10
char w[N][N] = {
"GKJSMOIUEW",
"ITFSOFCJFO",
"PAKJMWDRFA",
"MCHJOYIOPL",
"QWGTDXZEUI",
"AUTOMOBILE",
"XYZNIERUNE",
"TOYESBZCZR",
"LXACPTRWAA",
"MOMDADOOOR"
};
char *dict[] = {
"CAT",
"MOM",
"MOMO",
"AUTO",
"MOBILE",
"AUTOMOBILE",
"TON",
"RUN",
"OAA",
"ZROD",
"PAK",
"TOY",
"OIYOJ",
"CAR",
"BAT",
"PIG",
"PI",
};
void search_word(char *word)
{
int k;
int dsize = sizeof(dict) / sizeof(char *);
for (k = 0; k < dsize; k++) {
if (!strncmp(dict[k], word, strlen(dict[k])))
printf("Found : [%s]\n", dict[k]);
}
}
int main(int argc, char *argv[])
{
int x, y;
int i, j, k;
char word[N+1];
for (x = 0; x < N; x++) {
for (y = 0; y < N; y++) {
// Search left to right
for (i = x, j = y, k = 0; j < N; j++, k++)
word[k] = w[i][j];
word[k] = '\0';
search_word(word);
// Search right to left
for (i = x, j = y, k = 0; j >= 0; j--, k++)
word[k] = w[i][j];
word[k] = '\0';
search_word(word);
// Search top to bottom
for (i = x, j = y, k = 0; i < N; i++, k++)
word[k] = w[i][j];
word[k] = '\0';
search_word(word);
// Search bottom to top
for (i = x, j = y, k = 0; i >= 0; i--, k++)
word[k] = w[i][j];
word[k] = '\0';
search_word(word);
}
}
return 0;
}
In terms of the dictionary, I think you are going to want to use a trie to represent it. That way, you can stop once you run out of possible words. For example, once you hit something like xvj you want to stop (in the trie, you'd hit a dead end). Else you'd have to try every combination from every starting point, and that's a snooze-fest.
- Anonymous May 27, 2013