Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

A classic backtracking problem. Keep trying to find a path, if a deadend, back track using recursion.

#include<stdio.h>
#include<stdbool.h>
#include<string.h>

#define M 3
#define N 4

bool findpath(int m[M][N], char *str, int i, int j, int path[M][N])
{
	bool ret;

	if(!str || !(*str))
		return true;

	if(i < 0 || j < 0 || i > M || j > N)
		return false;

	if(path[i][j] == 1)
		return false;

	if(*str != m[i][j])
		return false;
	path[i][j] = 1;

	ret = findpath(m, str+1, i+1, j, path);
	if(ret == true)
		return ret;

	ret = findpath(m, str+1, i, j+1, path);
	if(ret == true)
		return ret;


	ret = findpath(m, str+1, i-1, j, path);
	if(ret == true)
		return ret;


	ret = findpath(m, str+1, i, j-1, path);
	if(ret == true)
		return ret;

	path[i][j] = 0;
	return false;
}

int main()
{
	bool ret;
	int i, j;
	char str[] = "follow";
	int m[M][N] =	{	{ 'o', 'f', 'a', 's' },
				{ 'l', 'x', 'q', 'w' },
				{ 'z', 'o', 'w', 'k' }		};
	int path[M][N] = {};

	for(i = 0; i < M; i++) {
		for(j = 0; j < N; j++) {
			if(m[i][j] == str[0]) {
				ret = findpath(m, str, i, j, path);
				if(ret) {
					printf("found\n"); return 0;
				}
			}
		}
	}
 }

- Brave Heart April 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

make sure to check your inputs too. Thats a big part of what they are checking you for (null pointers, string lengths, etc...)

Otherwise, well done

- rotinom April 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

why there is a need to save and check the path? if the input is "follllow", we should also return true.

- anonymous April 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Hi,
Your code is wrong. It works only when word starts from M[0][0]. In fact example case itself is not found.

- abhi April 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Use backtracking procedure for this one
1. start from each location, check for possible locations and match the character,
2. If position is OK repeat 1.

#include<stdio.h>
int FindPattern(int x,int y,char arr[x][y],int i,int j,char *,int pos);
int Check(int x,int y,char arr[x][y],int i,int j,char ch);
int main(){
	char arr[3][4]={"ofas","llqw","zowk"};
	char pat[]="love";
	int i,j;
	for(i=0;i<3;i++){
		for(j=0;j<4;j++){
			if(arr[i][j]==pat[0]){
				if(FindPattern(3,4,arr,i,j,pat,1)){
					printf("TRUE");	
					return 0;
				}
			}
		}
	}
	printf("FALSE");
	return 0;
}
int FindPattern(int x,int y,char arr[x][y],int i,int j,char *ch,int pos){
	if(ch[pos]==0){
		return 1;
	}
	if(i!=0&&arr[i-1][j]==ch[pos]){
		if(FindPattern(x,y,arr,i-1,j,ch,pos+1)) return 1;
	}
	if(i!=x-1&&arr[i+1][j]==ch[pos]){
		if(FindPattern(x,y,arr,i+1,j,ch,pos+1)) return 1;
	}
	if(j!=0&&arr[i][j-1]==ch[pos]){
		if(FindPattern(x,y,arr,i,j-1,ch,pos+1)) return 1;
	}
	if(j!=y-1&&arr[i][j+1]==ch[pos]){
		if(FindPattern(x,y,arr,i,j+1,ch,pos+1)) return 1;
	}
	return 0;
}

- Anonymous April 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Same code ... just marking visited flag to avoid repeated usage of that.

int check(char a[][N],int i,int j,char s[],int ind,int n)
{
    if(ind==n)
       return 1;
    if(i<0 || j<0 || i>=M || j>=N || a[i][j] != s[ind] || a[i][j]=='-')
       return 0;
    a[i][j]='-';
    return check(a,i+1,j,s,ind+1,n) || check(a,i-1,j,s,ind+1,n) || check(a,i,j+1,s,ind+1,n) || check(a,i,j-1,s,ind+1,n);
    a[i][j]=s[ind];
}

- Nitin April 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is it like the letters in the matrix side by side in horizontal line or vertical line or diagonal line?

- Anonymous April 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use backtracking:

class Exercise
{


	public static void main (String args[])
	{
		char[][] in = {{'s','o','b','c'},{'h','a','a','d'},{'x','d','a','x'}}; 
		boolean ans = canWordForm(in, "shadaab");
		System.out.println(ans);
	}

	public static boolean movePosition(char[][] charMatrix, String word, int r, int c){
		
		if(word.length() == 0)
			return true;
		
		
		//Move left
		if((c-1)>=0)
			if(charMatrix[r][c-1] == word.charAt(0)){
				{
					return movePosition(charMatrix, word.substring(1), r, (c-1));
				}
			}
		//Move right
		if ((c+1)<=charMatrix[0].length)
		{
			if(charMatrix[r][c+1] == word.charAt(0))
			{
				return movePosition(charMatrix, word.substring(1), r, (c+1));
			}
		}
		//Move up
		if((r-1)>=0)
		{
			if(charMatrix[r-1][c] == word.charAt(0))
			{
				return movePosition(charMatrix, word.substring(1), (r-1), c);
			}
		}
		//Move down
		if((r+1)<=charMatrix.length)
		{
			if(charMatrix[r+1][c] == word.charAt(0))
					{
				return movePosition(charMatrix, word.substring(1), (r+1), c);
					}
		}

		return false;
	}

	public static boolean canWordForm(char[][] charMatrix, String word){
		//boolean answer = false;

		if(charMatrix.length<=0 || charMatrix[0].length<=0)
			return true;
		if(word.length() == 0)
			return true;

		for(int i=0;i<charMatrix.length; i++){
			for(int j=0;j<charMatrix[0].length; j++){
				if(charMatrix[i][j] == word.charAt(0)){
					return  movePosition(charMatrix,word.substring(1), i,j);
				}

			}
		}

		return false;


	}


}

- Amir Shadaab April 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

import java.io.IOException;
import java.util.Scanner;
public class MatrixSearch1
{
static int s=3,t=3;
public static void main(String args[])throws IOException
{
int i,j,n;
String str;
@SuppressWarnings("resource")
Scanner br=new Scanner(System.in);
System.out.println("Enter the Elements of Matrix: ");
n=br.nextInt();
System.out.println("Enter the Elements for"+n+"*"+n+" Matrix:");
char[][] Mat=new char[n][n];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
Mat[i][j]=br.next().charAt(0);
}

}
System.out.println("Entered Matrix is: " );
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
System.out.print(Mat[i][j]+"\t");
}
System.out.println();
}
for(int a=0;a<=10;a++)
{
System.out.println("Enter the Search String: ");
str=br.next();
boolean result=check(Mat,str,n);
System.out.println(result);
}
}
public static boolean check(char[][] mat,String str,int n)
{
int m=0;
int l=str.length();
if(l==0)
{
return true;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(mat[i][j]==str.charAt(m))
{
l--;
if (position(mat,str,i,j,m,n,l) == true)
{
return true;
}
else
{
continue;
}

}
}
}
return false;
}
public static boolean position(char[][] mat,String str,int i,int j,int m,int n,int l)
{
m++;
if(l==0)
{
return true;
}
else
{
if(j-1>=0)
{
if(i!=s || (j-1)!=t)
{
if(mat[i][j-1] == str.charAt(m))
{
l--;
s=i;
t=j;
return position(mat, str, i, (j-1),m,n,l);
}
}
}
if ((j+1)<n)
{
if(i!=s || (j+1)!=t)
{
if(mat[i][j+1] == str.charAt(m))
{
l--;
s=i;
t=j;
return position(mat, str, i, (j+1),m,n,l);

}
}
}
if((i-1)>=0)
{
if((i-1) !=s || j !=t)
{
if(mat[i-1][j] == str.charAt(m))
{
l--;
s=i;
t=j;
return position(mat, str, (i-1), j,m,n,l);
}
}
}
if((i+1)<mat.length)
{
if((i+1) != s || j!=t)
{
if(mat[i+1][j]==str.charAt(m))
{
l--;
s=i;
t=j;
return position(mat, str, (i+1), j,m,n,l);
}
}
}
return false;
}
}
}

- Sarath Varun January 12, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about using array. Keep count for each char.
Reading is faster !

int _tmain(int argc, _TCHAR* argv[])
{
int count = 0;
int arr[128] = { 0 };
char ch;
bool flag = true;
char matrix[][4] = {"olz", "flo", "aqw", "swk"};
for (int i = 0; i < 4; i++)
{
for(int j = 0; j< 3; j++)
{
ch = matrix[i][j];
arr[(int)ch]++;
}
}
char strn[] = "follow";

while(ch != '\0')
{
ch = strn[count];
if (ch == '\0')
break;
if (arr[(int)ch] < 1)
{
flag = false;
break;
}
count++;
}
if (flag)
{
printf("exists");
}
return 0;
}

- aryasoumen April 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <string>
#include <vector>
#include <assert.h>

std::vector< std::vector<char> > mat =
 { {'o', 'f', 'a', 's' },
   {'l', 'l', 'q', 'w' },
   {'z', 'o', 'w', 'k'}
 };

bool is_next(int &row, int &col, const int maxrow,
                const int maxcol, const char nxt)
{
    assert(row >=0 && col >=0);

    if (row - 1 >= 0 && mat[row-1][col] == nxt) {
        row = row - 1;
        return true;
    }

    if (row + 1 < maxrow && mat[row + 1][col] == nxt) {
        row = row + 1;
        return true;
    }

    if (col -1 >= 0 && mat[row][col -1] == nxt) {
        col = col - 1;
        return true;
    }

    if (col + 1 < maxcol && mat[row][col + 1] == nxt) {
        col = col + 1;
        return true;
    }
}

bool findword_at(std::string &word, int &row, int &col,
                    const int maxrow, const int maxcol)
{
    return is_next(row, col, maxrow, maxcol, word[0]);
}

bool findword(std::string &word, int startrow, int startcol,
                const int maxrow, const int maxcol)
{
    for (int row=startrow; row < maxrow; ++row) {
        for (int col=startcol; col < maxcol; ++col) {
            bool ret = findword_at(word, row, col, maxrow, maxcol);
            if (ret) {
                mat[row][col] = 'X';

                /* found last letter */
                if (word.size() == 1)
                    return true;

                std::string wordorig = word;
                word = word.substr(1, word.size());
                bool subret = findword(word, row, col, maxrow, maxcol);
                if (!subret) {
                    word = wordorig;
                } else {
                    return true;
                }
            }
        }
    }

    return false;
}

int main()
{
    std::string word = "follow";

    bool ret = findword(word, 0, 0, 3, 4);
    if (ret)
        std::cout << " found";
    else
        std::cout << " not found";
}

- Anonymous March 18, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

need to check if they are adjacent and the number of each letter.

- Deo April 04, 2014 | Flag


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