Hackerrank Interview Question
Senior Software Development EngineersCountry: 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
if you start from 1 then you can only move to right or down... and you can visit next element only if the next one is smaller ..so on the right of 1 there are 2 and 3 which is bigger so you cant visit and if you go down there are also 2, 3.. so for 1..you can visit only one element which is itself....
1 2 3
1
2
here for 3, you cant move left but can go down, where there are 1 and 2 which are smaller.. so you can visit..so total is 3 itself, 1 and 2.. so you can write 3
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