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

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

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

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

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

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.

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

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

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

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?

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'}};
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){

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;

}

}``````

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

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

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

How about using array. Keep count for each char.

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

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

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

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

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.