## Amazon Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

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

``````public 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(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;
}
}``````

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

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

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

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]``````

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.