Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
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
why there is a need to save and check the path? if the input is "follllow", we should also return true.
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;
}
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];
}
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;
}
}
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;
}
}
}
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;
}
#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";
}
A classic backtracking problem. Keep trying to find a path, if a deadend, back track using recursion.
- Brave Heart April 04, 2014