Amazon Interview Question Software Engineers
Country: United States
Interview Type: In-Person
int[] dx = { -1, 1, 0, 0 };
int[] dy = { 0, 0, -1, 1 };
public int longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return 0;
int[][] mem = new int[matrix.length][matrix[0].length];
int longest = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
longest = Math.max(longest, dfs(matrix, i, j, mem));
}
}
return longest;
}
public int dfs(int[][] matrix, int i, int j, int[][] mem) {
if (mem[i][j] != 0)
return mem[i][j];
for (int m = 0; m < 4; m++) {
int x = i + dx[m];
int y = j + dy[m];
if (x >= 0 && y >= 0 && x < matrix.length && y < matrix[0].length && matrix[x][y] > matrix[i][j]) {
mem[i][j] = Math.max(mem[i][j], dfs(matrix, x, y, mem));
}
}
return ++mem[i][j];
}
public static int[][] sumMat(int sum) {
int[][] mat = new int[5][];
mat[0] = new int[] { 2, 5, 4, 6, 3 };
mat[1] = new int[] { 5, 4, 11, 22, 23 };
mat[2] = new int[] { 2, 14, 17, 2, 14 };
mat[3] = new int[] { 12, 14, 12, 1, 13 };
mat[4] = new int[] { 1, 5, 4, 6, 8 };
int[][] res = new int[5][];
for (int i = 0; i < 5; i++) res[i] = new int[5];
res[0][0] = 1;
matS(mat, res, 0, 0, mat[0][0], sum);
if (res[0][0] == 2)
res[0][0] = 1;
else
res[0][0] = 0;
return res;
}
public static void matS(int[][] mat, int[][] res, int x, int y, int curSum, int sum) {
if (res[0][0] == 1) {
int[] nx = new int[] { x - 1, x, x + 1, x };
int[] ny = new int[] { y, y - 1, y, y + 1 };
for (int i = 0; i < 4; i++) {
if (nx[i] >= 0 && ny[i] >= 0 && nx[i] < mat[0].Length && ny[i] < mat.Length &&
res[ny[i]][nx[i]] == 0 && res[0][0] == 1)
{
if (curSum + mat[ny[i]][nx[i]] == sum)
{
res[0][0] = 2;
res[ny[i]][nx[i]] = 1;
break;
}
else
if (curSum + mat[ny[i]][nx[i]] < sum)
{
res[ny[i]][nx[i]] = 1;
curSum += mat[ny[i]][nx[i]];
matS(mat, res, nx[i], ny[i], curSum, sum);
if (res[0][0] == 1)
{
curSum -= mat[ny[i]][nx[i]];
res[ny[i]][nx[i]] = 0;
}
}
}
}
}
}
BFS solution:
import random
(n, m) = (10, 15)
(mx,s) = ([random.randint(0, 9) for _ in xrange(n*m)], random.randint(1, 50))
(v,l,r) = ([0]*m*n, [[[0], mx[0]]], [])
while l:
nl = []
for [p, ps] in l:
if ps == s:
r = p
break
if ps < s:
pp = p[-1]
for np in [pp + d for d in [-1, 1, -m, m]
if 0<=pp+d<n*m and abs((pp+d)%m - pp%m)<2 and v[pp+d] == 0]:
v[np] = 1
nl += [[p + [np], ps + mx[np]]]
l = nl
def printm(mx):
print ""
for i in xrange(n):
print '[' + ' '.join(map(str, mx[i*m:i*m+m])) + ']'
print "target =", s
printm(mx)
if r:
printm([1 if i in r else 0 for i in xrange(n*m)])
Output:
target = 34
[9 1 1 6 9 1 4 8 5 3 2 5 9 4 4]
[7 1 6 6 3 6 9 3 3 7 0 9 3 0 1]
[9 2 6 7 3 7 0 7 8 1 6 7 0 7 5]
[0 3 3 3 4 2 9 4 8 5 4 5 0 9 0]
[4 3 1 4 4 4 5 0 6 9 5 7 8 7 5]
[4 7 1 4 6 5 4 0 1 9 0 1 8 6 0]
[6 8 5 9 7 8 3 6 7 5 5 1 0 4 4]
[1 6 2 9 8 2 5 9 7 4 9 9 7 5 5]
[9 1 9 9 0 9 5 6 4 9 4 4 9 9 9]
[4 1 5 3 1 5 9 0 2 4 1 2 8 4 3]
[1 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
- huehuehuehue June 14, 2018public class SumInMatrix { public static void main(String[] args) { int[][] input = {{9, 1, 1, 6, 9, 1, 4, 8, 5, 3, 2, 5, 9, 4, 4}, {7, 1, 6, 6, 3, 6, 9, 3, 3, 7, 0, 9, 3, 0, 1}, {9, 2, 6, 7, 3, 7, 0, 7, 8, 1, 6, 7, 0, 7, 5}, {0, 3, 3, 3, 4, 2, 9, 4, 8, 5, 4, 5, 0, 9, 0}, {4, 3, 1, 4, 4, 4, 5, 0, 6, 9, 5, 7, 8, 7, 5}, {4, 7, 1, 4, 6, 5, 4, 0, 1, 9, 0, 1, 8, 6, 0}, {6, 8, 5, 9, 7, 8, 3, 6, 7, 5, 5, 1, 0, 4, 4}, {1, 6, 2, 9, 8, 2, 5, 9, 7, 4, 9, 9, 7, 5, 5}, {9, 1, 9, 9, 0, 9, 5, 6, 4, 9, 4, 4, 9, 9, 9}, {4, 1, 5, 3, 1, 5, 9, 0, 2, 4, 1, 2, 8, 4, 3}}; int sum = 34; int[][] output = new int[input.length][input[0].length]; if(findPath(input, output, sum, 0,0)) PrintMatrix.printMatrix(output); } public static boolean findPath(int[][] matrix, int[][] output, int sum, int r, int c){ System.out.println("Row: "+r+", Col: "+c+" Target: "+sum); output[r][c] = 1; if(sum-matrix[r][c]==0) { return true; }else if(sum-matrix[r][c]<0){ output[r][c] = 0; return false; } if(r+1<matrix.length && output[r+1][c]!=1){ boolean bottom = findPath(matrix, output, sum-matrix[r][c], r+1, c); if(bottom) return bottom; } if(r-1>-1 && output[r-1][c]!=1){ boolean top = findPath(matrix, output, sum-matrix[r][c], r-1, c); if(top) return top; } if(c-1>-1 && output[1][c-1]!=1){ boolean left = findPath(matrix, output, sum-matrix[r][c], r, c-1); if(left) return left; } if(c+1<matrix[0].length && output[r][c+1]!=1){ boolean right = findPath(matrix, output, sum-matrix[r][c], r, c+1); if(right) return right; } output[r][c] = 0; return false; } }