Amazon Interview Question
SDE1sCountry: United States
Interview Type: In-Person
Backtracking show 4 solutions:
[(0, 1), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5)]
[(0, 1), (1, 1), (1, 2), (2, 2), (3, 2), (3, 3)]
[(0, 1), (1, 1), (2, 1), (2, 2), (3, 2), (3, 3)]
[(0, 1), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)]
found words: 4
private static int findAWordInAMatrix(String word, String[][] matrix) {
int numOcurrences = 0;
char firstLetter = word.charAt(0);
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (firstLetter == matrix[i][j].charAt(0)) {
numOcurrences+= easyRecursiveSolution(matrix, word.substring(1), i, j);
}
}
}
return numOcurrences;
}
private static int easyRecursiveSolution(String[][] matrix, String word, int i, int j) {
int numOcurrences = 0;
if (word.length() == 0) {
return 1;
}
if(i < matrix.length - 1 && matrix[i+1][j].charAt(0) == word.charAt(0)) { // move down
numOcurrences+= easyRecursiveSolution(matrix, word.substring(1), i+1, j);
}
if(j < matrix[i].length - 1 && matrix[i][j+1].charAt(0) == word.charAt(0)) { // move right
numOcurrences+= easyRecursiveSolution(matrix, word.substring(1), i, j+1);
}
if(i < matrix.length - 1 && j < matrix[i].length - 1 && matrix[i+1][j+1].charAt(0) == word.charAt(0)) { // move donw/right
numOcurrences+= easyRecursiveSolution(matrix, word.substring(1), i+1, j+1);
}
return numOcurrences;
}
static int count;
void search(char arr[][6], int xlen, int ylen, char *str, int slen,
int i, int j, int k) {
if (i == xlen || j == ylen)
return;
if (arr[i][j] == str[k]) {
if (k == slen - 1) {
count++;
return;
}
k++;
}
search(arr, xlen, ylen, str, slen, i + 1, j, k);
search(arr, xlen, ylen, str, slen, i, j + 1, k);
search(arr, xlen, ylen, str, slen, i + 1, j + 1, k);
}
int main(int argc, char *argv[]) {
char input[4][6] = {{'w','s','r','t','g','g'},
{'a','a','c','h','i','n'},
{'k','c','h','u','j','j'},
{'o','h','i','n','y','q'}};
char str[] = {'s','a','c','h','i','n'};
search(input, 4, 6, str, 6, 0, 0, 0);
printf("found %s %d times\n", str, count);
return 0;
}
char mat[4][6] = {
{'w', 's', 'r', 't', 'g', 'g'},
{'s', 'a', 'c', 'h', 'i', 'n'},
{'k', 'c', 'h', 'u', 'j', 'j'},
{'o', 'h', 'i', 'n', 'y', 'q'}
};
int srl = 6;
int totalcount = 0;
char matchstr[6] = "sachin";
int m = 4, n = 6;
char
strsrch (int i, int j, int strmatchcnt)
{
int rcr = 0, rcb = 0, rcd = 0;
if (j > n-1) {
return 1;
}
if (i > m-1) {
return 1;
}
if (strmatchcnt%(srl) == 0) {
printf(" F<%c> (%d %d )\n", matchstr[strmatchcnt-1], i, j);
totalcount +=1;
return 1;
}
if (matchstr[strmatchcnt] == mat[i][j+1]) {
printf(" R<%c ( %d %d)>\n ", matchstr[strmatchcnt-1], i , j);
rcr = strsrch(i,j+1, strmatchcnt+1);
if (rcr == 1) {
return 0;
}
}
if (matchstr[strmatchcnt] == mat[i+1][j]) {
printf(" B<%c> (%d %d)\n ", matchstr[strmatchcnt-1], i, j);
rcb = strsrch(i+1, j, strmatchcnt+1);
if (rcb == 1) {
return 0;
}
}
if (matchstr[strmatchcnt] == mat[i+1][j+1]) {
printf(" D<%c> (%d %d)", matchstr[strmatchcnt-1], i, j);
rcd = strsrch(i+1, j+1, strmatchcnt+1);
if (rcd == 1) {
return 0;
}
}
if (!rcr || !rcb || !rcd) {
return 0;
}
return -1;
}
main ()
{
int i, j;
i = 0;
while (i < m) {
j = 0;
while (j < n) {
if (mat[i][j] == matchstr[0]) {
strsrch(i, j, 1);
}
j++;
}
i++;
}
printf("Match str %d\n", totalcount);
}
I was trying to find what I did wrong in my code since my code returned 4 times instead of 3 times. I now see I am not the only one.
The following is the working code in Python
def find_word2(matrix, word, hsize, vsize):
result = 0
s = datetime.datetime.now()
for i in range(0, len(matrix)):
result += search_matrix2(word, matrix, hsize, vsize, i, 0, 0)
e = datetime.datetime.now()
lapsed = e - s
print word + " showed up " + str(result) + " times : took " + str(lapsed.microseconds) + " ms"
def search_matrix2(word, matrix, hsize, vsize, hpos, vpos, index):
if (vpos >= vsize or hpos >= hsize or matrix[vpos][hpos] != word[index]):
return 0
if (index == len(word)-1):
return 1
return search_matrix2(word, matrix, hsize, vsize, hpos+1, vpos, index+1) + search_matrix2(word, matrix, hsize, vsize, hpos, vpos+1, index+1) + search_matrix2(word, matrix, hsize, vsize, hpos+1, vpos+1, index+1)
public const int row = 6, col = 5;
public const int compare = 4;
static void Main(string[] args)
{
char[,] array = new char[row, col]
{
{ 'j', 's', 'n', 'o', 'w' }, { 'a', 'n', 'g', 'x', 't' }, { 'c', 't', 'o', 'o', 'n' },
{ 's', 'n', 'o', 'w', 'a' }, { 's', 'k', 'w', 'b', 'c' }, { 'd', 'e', 'f', 'g', 'h' }
};
char[] str = new char[compare] {'s', 'n', 'o', 'w'};
FindMatch(array, row, col, str);
Console.ReadKey();
}
public static void FindMatch(char[,] array, int xb, int yb, char[] str)
{
int result = 0;
for (int i = 0; i < xb; i++)
{
for (int j = 0; j < yb; j++)
{
if (array[i, j] == str[0])
{
result +=Find(array, i, j, str, 0);
}
}
}
Console.WriteLine(result);
}
private static int Find(char[,] array, int x, int y, char[] str, int pos)
{
if (x >= row || y >= col)
{
return 0;
}
if (array[x, y] == str[pos] && pos == compare - 1 )
{
return 1;
}
int result = 0;
if (array[x, y] == str[pos])
{
result += Find(array, x, y + 1, str, pos + 1);
result += Find(array, x+1, y, str, pos + 1);
result += Find(array, x+1, y + 1, str, pos + 1);
}
return result;
}
public class BackTracking {
public static int count = 0;
public void backtrackPat(char[][] mat, int i, int j, int ilen, int jlen, char[] pat, int k, int klen ){
if(i == ilen || j == jlen)
return;
if(mat[i][j] == pat[k]){
if(k == klen-1){
System.out.println(i + " " + j);
BackTracking.count ++;
return;
}
k ++;
}
backtrackPat(mat, i, j + 1, ilen, jlen, pat, k, klen);
backtrackPat(mat, i + 1, j, ilen, jlen, pat, k, klen);
}
public static void main(String[] args){
char[][] mat = {{'b','a','b','b','c'},{'e','a','c','e','d'},{'e','t','f','a','g'},{'h','i','j','t','k'}};
char[] pat = {'b','e','a','t'};
BackTracking bt = new BackTracking();
bt.backtrackPat(mat, 0, 0, 4, 5, pat, 0, 4 );
System.out.println(BackTracking.count);
}
}
This prints 8 for some reason. It should print 2. Can anyone help figure out the problem.
static int countOfWord=0;
static char[][] matrix=new char[][]{{'w','s','r','t','g','g'},
{'a','a','c','h','i','n'},
{'k','c','h','u','j','j'},
{'o','h','i','n','y','q'}};
int searchWordInMatrixFromAGivenIJ(char[][] matrix,int m,int n,char[] word, int curVal,int iVal, int jVal){
if(curVal==word.length-1 && word[curVal]==matrix[iVal][jVal]){
countOfWord++;
}
else if(word[curVal]==matrix[iVal][jVal] && curVal!=word.length-1){
System.out.println("Found char:"+word[curVal]+" ival="+iVal+"jVal="+jVal);
if(iVal!=m-1){
searchWordInMatrixFromAGivenIJ(matrix,m,n,word,curVal+1,iVal+1,jVal);
}
if(jVal!=n-1){
searchWordInMatrixFromAGivenIJ(matrix,m,n,word,curVal+1,iVal,jVal+1);
}
if((jVal!=n-1) && (iVal!=m-1)){
searchWordInMatrixFromAGivenIJ(matrix,m,n,word,curVal+1,iVal+1,jVal+1);
}
}
return countOfWord;
}
int searchWordInMatrix(char[][] matrix,int m,int n,char[] word){
if(m==0 || n==0 || word.length==0){
return 0;
}
int count=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
countOfWord=0;
count+=searchWordInMatrixFromAGivenIJ(matrix,m,n,word,0,i,j);
}
}
return count;
}
Brute force, I was able to get a solution w/o too much trouble?
- Teja April 15, 2014