Amazon Interview Question for SDE1s


Country: United States
Interview Type: In-Person




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

Brute force, I was able to get a solution w/o too much trouble?

public int find(char[,] array, int x, int y, int charsFound, char[] textToFind)
  {
   
    if (x >= array.GetLength(0) || y >= array.GetLength(1)) { return 0; }
   
    if(array[x, y] == textToFind[charsFound]) {
      charsFound++;
    }
    else {
      charsFound = 0;
    }

    int found = 0;
   
    if (charsFound == textToFind.Length) {
      found = found + 1;
      charsFound = 0;
    }

    found = found + find(array,
                         x + 1,
                         y,
                         charsFound,
                         textToFind);       

    found = found + find(array,
                         x + 1,
                         y + 1,
                         charsFound,
                         textToFind);

    found = found + find(array,
                         x,
                         y + 1,
                         charsFound,
                         textToFind);
    if (found > 0) {
      Console.WriteLine("found at " + x + " " + y + " " + found);
    }
    return found;
  }

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

what is the time and space(assuming system stack) complexity of the code?

- vishal July 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can use backtracking.....

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

the question is a little confuse.
here has some idea.
if the question is ask to count number of all the words in the matrix, we can use Trie tree to help to count the number for all the words.
if he quesion is ask to count number of given word, we can directly DFS.

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

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

- m@}{ April 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please post code for this?

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

Sachin can be found in 4 ways in the given matrix.

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

can we access the static variable using this method ? If yes then why?

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

How can we do it using BFS.
Help...No thoughts...

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

Use mouse in a maze method...

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

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

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

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

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

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

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

You'd find sachin 4 times in that example matrix.

- Colin Jack April 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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)

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

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

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

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.

- geek May 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- abhishek June 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Traverse the matrix, and add all the suffix to a TRIE, store the number of the occurence in the node
2) Traverse the TRIE by a word
order is O(E+N)?

- nishiken July 23, 2014 | 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