Amazon Interview Question
Software EngineersCountry: 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, 2018