## Hackerrank Interview Question

Senior Software Development Engineers**Country:**India

**Interview Type:**Written Test

def visiting_matrix(matrix):

def compute_successors(x, y):

res = []

for x1, y1 in [ (0, 1), (1, 0) ]:

x2 = x + x1

y2 = y + y1

if x2 >= len(matrix): x2 -= len(matrix)

if y2 >= len(matrix): y2 -= len(matrix)

res.append((x2, y2))

return res

r = [ [ 0 ] * len(matrix) for _ in xrange(len(matrix)) ]

positions = [ (x, y) for x in xrange(len(matrix))

for y in xrange(len(matrix)) ]

for (x, y) in positions:

total = 0

goals = [ (x, y) ]

for g in goals:

total += 1

successors = compute_successors(g[0], g[1])

for s in successors:

if matrix[g[0]][g[1]] > matrix[s[0]][s[1]]:

goals.append(s)

r[x][y] = total

return r

```
function solution(matrix) {
function p(row, col, initialValue) {
if (Math.max(row, col) >= matrix.length || matrix[row][col] >= initialValue) return 0;
return 1 + Math.max(p(row + 1, col, initialValue), p(row, col + 1, initialValue));
}
let result = [];
for (let r = 0; r < matrix.length; r++){
result[r] = [];
for (let c = 0; c < matrix.length; c++){
result[r][c] = 1 + Math.max(p(r + 1, c, matrix[r][c]), p(r, c + 1, matrix[r][c]));
}
}
return result;
}
```

```
function solution(matrix) {
function p(row, col, initialValue) {
if (Math.max(row, col) >= matrix.length || matrix[row][col] >= initialValue) return 0;
return 1 + Math.max(p(row + 1, col, initialValue), p(row, col + 1, initialValue));
}
let result = [];
for (let r = 0; r < matrix.length; r++){
result[r] = [];
for (let c = 0; c < matrix.length; c++){
result[r][c] = 1 + Math.max(p(r + 1, c, matrix[r][c]), p(r, c + 1, matrix[r][c]));
}
}
return result;
}
```

```
function solution(matrix) {
function p(row, col, initialValue) {
if (Math.max(row, col) >= matrix.length || matrix[row][col] >= initialValue) return 0;
return 1 + Math.max(p(row + 1, col, initialValue), p(row, col + 1, initialValue));
}
let result = [];
for (let r = 0; r < matrix.length; r++){
result[r] = [];
for (let c = 0; c < matrix.length; c++){
result[r][c] = 1 + Math.max(p(r + 1, c, matrix[r][c]), p(r, c + 1, matrix[r][c]));
}
}
return result;
}
```

A possible optimization is to check if the resolution matrix already has computed a solution and add that value instead computing all the possible paths when adding a new element to the goals list

- Fernando May 15, 2017