## Amazon Interview Question

• 2

Country: India

Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

Given n^2 elements in the 2D array, the complexity is O(n^4) for this solution.. right?

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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)
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]``````

Comment hidden because of low score. Click to expand.
0

May be this would suffice in place of the last part of iterating over strings?

``````for base_str in base_str_set
if base_st in dictx
print base_str``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

variation of flood fill algorithm

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can construct a trie where every node of a trie has the prefix till that point as its key. Then a BFS on a trie can help us find every node in the dictionary.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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[],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[],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[],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[],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={'c','a','t','g','o','d','f','b','r'};
trie.matchRow(arr,3,3);
trie.matchCol(arr,3,3);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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",
};

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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.