## Amazon Interview Question for Software Developers

Country: United States
Interview Type: Phone Interview

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

I don't think there's a 'clever' or algorithmic way to solve this (happy to be corrected), but brute force would work well here.
Following is the code

``````public class Find2dPattern
{
private int[][] input;
private int[][] pattern;

public boolean patternExists(final int[][] input, final int[][] pattern)
{
//Errors and edge conditions.
if(input == null || pattern == null || input.length == 0 || input[0].length == 0 || pattern.length==0 || pattern[0].length == 0) { throw new IllegalArgumentException();}
if(input.length < pattern.length) { return false; }
if(input[0].length < pattern[0].length) { return false; }
if(input.length == pattern.length && input[0].length == pattern[0].length && input[0][0] != pattern[0][0]) { return false;}
else
{
this.input = input;
this.pattern = pattern;
for(int i = 0; i < input.length; i++)
for(int j = 0; j < input[i].length; j++)
{
if(input[i][j] == pattern[0][0]) //found potential
{
if(isMatch(i,j))
return true;
}
}
}

return false;
}

private boolean isMatch(int row, int column)
{
//Check for boundary
if(row + pattern.length-1 > input.length)
return false;
if(column + pattern[0].length-1 > input[0].length)
return false;

int k = 0 ; int l = 0;

while(k < pattern.length)
{
while(l < pattern[k].length)
{
if(input[row][column] != pattern[k][l]) //done
return false;
else
{
column++;
l++;
}
}
row++;
k++;
}
return true;

}

}``````

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

It is 2D version of Rabin-Karp algorithm. It's complexity is O(n) in 1D case. In 2D case it should be O(n x m)

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

One simply need find the the matching of the first row of the 2D pattern, then check if the below rows match the rest pattern or not. The time complexity is n*m, each cell need be touched just once.

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

right.

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

aaaaaaaaa
aaaaaaaaa
aabaabaab
aaaaaaaaa
aaaaaaaaa
aabaabaab

vs

aaa
aaa
aaa

Now, imagine the same, but with more rows. In other words: just when you think you are about to find that the pattern is right, it turns out it's not.

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

def find_pattern(pattern, digits):
"""
Digits is a list of rows of strings
"""
if not len(digits) or not len(pattern):
return False
# row length
span_digits = len(digits[0])
span_pattern = len(pattern[0])
len_pattern = len(pattern)
all_digits = ''.join(digits)
for ind in xrange(len(all_digits)):
part = 0
if all_digits[ind:ind + span_pattern] == pattern[part]:
if len(pattern) == 1:
return True
cur_ind = ind + span_digits
part += 1
while all_digits[cur_ind:cur_ind + span_pattern] == pattern[part]:
part += 1
cur_ind += span_digits
if len(pattern) == part:
return True

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

``````def find_pattern(pattern, digits):
"""
Digits is a list of rows of strings
"""
if not len(digits) or not len(pattern):
return False
# row length
span_digits = len(digits[0])
span_pattern = len(pattern[0])
len_pattern = len(pattern)
all_digits = ''.join(digits)
for ind in xrange(len(all_digits)):
part = 0
if all_digits[ind:ind + span_pattern] == pattern[part]:
if len(pattern) == 1:
return True
cur_ind = ind + span_digits
part += 1
while all_digits[cur_ind:cur_ind + span_pattern] == pattern[part]:
part += 1
cur_ind += span_digits
if len(pattern) == part:
return True``````

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

``````def find_pattern(pattern, digits):
"""
Digits is a list of rows of strings
"""
if not len(digits) or not len(pattern):
return False
# row length
span_digits = len(digits[0])
span_pattern = len(pattern[0])
len_pattern = len(pattern)
all_digits = ''.join(digits)
for ind in xrange(len(all_digits)):
part = 0
if all_digits[ind:ind + span_pattern] == pattern[part]:
if len(pattern) == 1:
return True
cur_ind = ind + span_digits
part += 1
while all_digits[cur_ind:cur_ind + span_pattern] == pattern[part]:
part += 1
cur_ind += span_digits
if len(pattern) == part:
return True``````

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

``````def find_pattern(pattern, digits):
"""
Digits is a list of rows of strings
"""
if not len(digits) or not len(pattern):
return False
# row length
span_digits = len(digits[0])
span_pattern = len(pattern[0])
len_pattern = len(pattern)
all_digits = ''.join(digits)
for ind in xrange(len(all_digits)):
part = 0
if all_digits[ind:ind + span_pattern] == pattern[part]:
if len(pattern) == 1:
return True
cur_ind = ind + span_digits
part += 1
while all_digits[cur_ind:cur_ind + span_pattern] == pattern[part]:
part += 1
cur_ind += span_digits
if len(pattern) == part:
return True``````

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

``````def find_pattern(pattern, digits):
"""
Digits is a list of rows of strings
"""
if not len(digits) or not len(pattern):
return False
# row length
span_digits = len(digits[0])
span_pattern = len(pattern[0])
len_pattern = len(pattern)
all_digits = ''.join(digits)
for ind in xrange(len(all_digits)):
part = 0
if all_digits[ind:ind + span_pattern] == pattern[part]:
if len(pattern) == 1:
return True
cur_ind = ind + span_digits
part += 1
while all_digits[cur_ind:cur_ind + span_pattern] == pattern[part]:
part += 1
cur_ind += span_digits
if len(pattern) == part:
return True``````

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

char *srcStr[] = { "7283455864",
..
"4607924137",
NULL};

char *patStr[] = {"950", 384", 353", NULL};

int occurCnt(char *str, char *subStr)
{
int cnt=0;

char *p = str;
while (p!=NULL)
{
p = strstr(p, subStr);
if (p!=NULL)
cnt++;
}
return cnt;
}

main()
{
int i, j;
int n;
for(j=0; patStr[j]!=NULL; j++)
{
n=0;
for(i=0; srcStr[i]!=NULL; i++)
n += ocurCnt(srcStr[i], patStr[j]);
printf("Pattern [%s] occured at %d times\n", patStr[j], n);
};
}

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

If there are no restrictions on the language to be used, I think Python would work best here.

1) Just search through each line:
line.find(950) # search for the exact match first
2) If match is made - Parse the line and find the pattern
3) If no match go to the next line and repeat

Based on the needs of the algorithm,
> You can simply run through lines counting the number of times a match is made
> If you have to extract it - it is more work

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

I think that this is 2D pattern matching problem . Brute force approach leads to O(n1*n2*m1*m2) where n1 - number rows in matrix, n2 - columns and m1 - rows in submatrix m2 - columns in submatrix;
If we use string pattern matching algorithms like Rabin Karp and KMP complexity could fall to O(n1*n2 +m1*m2). All depends on what an interviewer expects to be discussed and written on 45 minutes phone interview

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

more careful analysis gives O(n*m) for brute force.

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

Here is one approach with complexity O(m1*n1 +m2*n2) without using Rabin Karp fingerprints. Take the whole matrix and create one directional array as concatenating rows with some character which is not digit (to separate row ends). Then search with Acho Korasic for all occurence of each row of pattern in matrix vector and store where you find row match in some addtional two dimensional array of matrix size Then next phase is to iterate through all this additional matrix column by column and to check if there is a collumn with consecutive numbers (this means consecutive pattern rows because each number is a label of pattern's row)

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

what are m1,n1,m2 and n2 here in O(m1*n1 +m2*n2)?

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

It counts how many times the pattern is present (4 directions, brute force)

``````public class PatternSearcher{

public static void main(String[] args) {
int[][] matrix = new int[][]{
{7,2,8,3,4,5,5,8,6,4},
{6,7,3,1,1,5,8,6,1,9},
{8,9,8,8,2,4,2,6,4,3},
{3,8,3,9,5,0,5,3,2,4},
{9,5,0,9,5,0,5,8,1,3},
{3,8,4,3,8,4,5,3,8,4},
{6,4,7,3,5,3,0,2,9,3},
{7,0,5,3,1,0,6,6,0,1},
{0,8,3,4,2,8,2,9,5,6},
{4,6,0,7,9,2,4,1,3,7}
};

int[][] patterns = new int[][] {
{ 9, 5, 0 },
{ 3, 8, 4 },
{ 3, 5, 3 } };

System.out.println(count(matrix, patterns));

}

public static int count(int[][] matrix, int[][] patterns) {
int result = 0;
for (int r = 0; r < matrix.length; r++)
for (int c = 0; c < matrix[r].length; c++)
for (int[] p : patterns)
if (matrix[r][c] == p[0])
result += localCount(matrix, r, c, p);

return result;
}

private static boolean isValid(int[][] matrix, int r, int c) {
return r >= 0 && c >= 0 && r < matrix.length && c < matrix[0].length;
}

private static int localCount(int[][] matrix, int r, int c, int[] pattern) {

Boolean[] UDLR = new Boolean[] { true, true, true, true };

for (int i = 0; i < pattern.length; i++) {
UDLR[0] &= isValid(matrix, r - i, c)
&& matrix[r - i][c] == pattern[i];
UDLR[1] &= isValid(matrix, r + i, c)
&& matrix[r + i][c] == pattern[i];
UDLR[2] &= isValid(matrix, r, c - i)
&& matrix[r][c - i] == pattern[i];
UDLR[3] &= isValid(matrix, r, c + i)
&& matrix[r][c + i] == pattern[i];
}

int counter = 0;
for (int i = 0; i < 4; i++)
if (UDLR[i])
counter++;

return counter;

}

}``````

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

c# implementation.
O(n*m).

``````private static List<int[]> Find( int[,] arr, int[,] pattern ) {
var pattCol = 0;
var startCoords = new int[ 2 ] { -1, -1 };

for ( int i = 0; i < arr.GetLength( 0 ); i++ ) {
for ( int j = 0; j < arr.GetLength( 1 ); j++ ) {
if ( j > pattCol + ( arr.GetLength( 1 ) - pattern.GetLength( 1 ) ) ) {
break;
}

if ( arr[ i, j ] != pattern[ 0, pattCol ] ) {
startCoords = new[] { -1, -1 };
if ( pattCol != 0 ) {
j--;
pattCol = 0;
}
continue;
}

var pattRow = 0;
var colMatch = true;
for ( int k = i + 1; k < pattern.GetLength( 0 ) + i && k < arr.GetLength( 0 ); k++ ) {
pattRow++;
if ( arr[ k, j ] != pattern[ pattRow, pattCol ] ) {
colMatch = false; break;
}
}
if ( colMatch ) {
if ( pattCol == pattern.GetLength( 1 ) - 1 ) {
return new List<int[]> { startCoords, new [] { i + pattern.GetLength( 0 ) - 1, j } };
}
if ( startCoords[ 0 ] == -1 ) { startCoords = new [] { i, j }; }
pattCol++;
} else {
startCoords = new[] { -1, -1 };
pattCol = 0;
}
}
}
return null;
}``````

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

``````public bool PatterExist(int[,] matrix, int[,] pattern)
{
if (matrix == null || matrix.Length == 0)
return false;
if (pattern == null || pattern.Length == 0)
return false;

int n = matrix.GetLength(0) - pattern.GetLength(0);
int m = matrix.GetLength(1) - pattern.GetLength(1);
for (int i=0; i < n; i++)
for (int j=0; j < m; j++)
if (CheckPattern(matrix, pattern, i, j))
return true;
return false;
}

private bool CheckPattern(int[,] matrix, int[,] pattern, int row, int col)
{
for (int i = 0; i < pattern.GetLength(0); i++)
for (int j = 0; j < pattern.GetLength(1); j++)
if (matrix[row + i, col + j] != pattern[i, j])
return false;
return true;
}``````

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

``````package company.amazon;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class PatternFinderIn2DArray {
int[][] arr = {{9,5,3,5,3,8,4},
{3,8,9,5,0,8,4}};
int row = 2, col = 7;
public void find(int[][]arr, Map<String, Integer> patterns) {
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
Iterator<String> it = patterns.keySet().iterator();
while(it.hasNext()) {
String key = it.next();
char[] arrStr = key.toCharArray();
int idx = patterns.get(key);
if((arrStr[idx]+"").equals(arr[i][j]+"")) {
++idx;
if(idx == key.length()) {
System.out.println("Found "+key+", at row:"+i+",col:"+(j-key.length()+1));
idx = 0;
}
patterns.put(key, idx);
} else {
if(idx > 0) {
idx = 0;
patterns.put(key, idx);
}
}
}
}
}
}
public static void main(String[] args) {
PatternFinderIn2DArray util = new PatternFinderIn2DArray();
Map<String,Integer> patterns = new HashMap<String, Integer>();
patterns.put("950", 0);
patterns.put("384", 0);
patterns.put("353", 0);
util.find(util.arr, patterns);
}
}``````

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

``````int fun(int *i, int *j){
for (int ii = 0; ii < Pattern_size; ii++){
for (int jj = 0; jj < Pattern_size; jj++){
if (arr[ii][jj] != arr_main[ii + *i][jj + *j]) return -1;
}
}
return 0;
}
int fun1(int *i, int *j, int MainMatrixSize){
for (*i = 0; *i < MainMatrixSize; (*i)++){
for (*j = 0; *j < MainMatrixSize; (*j)++){
if(fun(i, j) == 0) return 0;
}
}
return -1;
}``````

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

MainMatrixSize = MainMatrixSize - Pattern_size;

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

bool scan(vector<string> &grid, int rows, vector<string> & sub_grid, int sub_rows) {

for(int i=0; i<rows; i++) {
int x=0;
//cout << " Processing : " << grid[i] << endl;
for(int j=0; j<sub_rows; j++) {
x = grid[i].find(sub_grid[j]);
if(x == -1)
break;
int k=0;
//cout << x << endl;
for(k=0;k<sub_rows-1;k++) {
string str = grid[i+k+1].substr(x,sub_grid[0].size());
//cout << str << endl;
if(str != sub_grid[j+k+1]) {
j=sub_rows+1;
break;
}
}

if(k>=sub_rows-1)
return true;
}
//cout << " x is " << x << endl;
if(x!= -1) {
string spaces;
//for(int z=0;z<x+sub_grid[0].size();z++)
spaces.push_back('a');

//cout << "spaces : " << spaces << endl;
//grid[i].replace(0,x+sub_grid[0].size(),spaces);
grid[i].replace(x,1,spaces);

//cout << " string after replacing is : " << grid[i] << endl;
i--;
continue;
}

}
return false;
}

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

I like how, with all of everyone's math reasoning above, based on my testing, only two of any of the implementations above actually work.

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.