Amazon Interview Question


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.

- Anonymous May 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Aasen May 28, 2013 | Flag
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.

- ChaoSXDemon May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

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

- Murali Mohan May 28, 2013 | Flag
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

- Ajay May 29, 2013 | Flag Reply
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[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]

- whatevva' May 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- mojoman May 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

variation of flood fill algorithm

- algos May 27, 2013 | Flag Reply
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.

- whatevva' May 27, 2013 | Flag Reply
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.

- Anonymous May 28, 2013 | Flag Reply
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[][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);
}

- sid June 02, 2013 | Flag Reply
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",
	"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;
}

- sangeet.kumar June 08, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More