60 mins:
1 question bout myself.
1 coding question:
Given a grid of n * m
A robot starts at the left top corner and can move only right or down.
Define how many possible ways exist for this robot to reach the bottom right corner.
P.S.
grid is filled with 0.
no obstacles.
no need to return the path or max/min path - just possible ways from the left top to the borrom right corner.
Example:
[0, 0]
[0, 0]
result = 2
/*
1 way to reach the right bottom is to move right then down
2 way to reach the right bottom is to move down then right
*/
[0, 0]
[0, 0]
[0, 0]
result = 3
/*
1 way to reach the right bottom is to move right - down - down
2 way to reach the right bottom is to move down - right - right
3 way to reach the right bottom is to move down - right - down
*/This question is a close relative of a Pascal's Triangle.
An interviewer helped me to come up with the solution using dynamic programming starting with a grid of size [0] and adding each element and seing how many possible ways the robot has:
[0] // only 1 way is possible [1]
/* add more elements */
[0, 0] // still one way [1, 1]
/* add more elements */
[0, 0, 0] // still one way [1, 1, 1]
/* add more elements */
[0, 0, 0]
[0]
// still 1 way = >
[1, 1, 1]
[1]
/* add more elements */
[0, 0, 0]
[0, 0]
// 2 ways (r-d, d-r) = >
[1, 1, 1]
[1, 2]
/* add more elements */
[0, 0, 0]
[0, 0, 0]
// 3 ways (r-r-d, d-r-r, r-d-r)= >
[1, 1, 1]
[1, 2, 3]
/* add more elements */
[0, 0, 0]
[0, 0, 0]
[0, 0, 0]
// 6 ways = >
[1, 1, 1]
[1, 2, 3]
[1, 3, 6]Notice that each next element is a sum of the left and the top one.
I absolutely failed to come up with the logic, but it was very easy to write code when I understood the pattern.