Amazon Interview Question Software Developers
Country: United States
Interview Type: Phone Interview
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.
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
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
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
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
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
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);
};
}
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
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
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)
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;
}
}
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;
}
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;
}
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);
}
}
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;
}
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;
}
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
- fayezelfar February 05, 2016public 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; } }