Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
public static int countPath(int m, int n) {
int [] [] count = new int[m][n];
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if (i == 0 || j == 0)
count[i][j] = 1;
else
count[i][j] = count[i-1][j]+count[i][j-1]+count[i-1][j-1];
}
}
return count[m-1][n-1];
}
If all cells are accessible (which is what your code assume), there is no need for all this...
Every path has (m-1) downward sections and (n-1) rightward sections.
But in total (m-1) + (n-1) = m+n-2 sections
Answer is (m+n-2) choose {either (m-1) or (n-1) doesn't matter}
Why? Because we are counting the number of ways to build a path (i.e., choosing positions for downward paths and filling rest as rightward OR vice versa).
"choose" binomial coefficient can be found using dinamic programming using Pascal's identity and methods similar to Fibonacci sequences' code.
Also, if the question had some "dead" spots in the matrix, then your code adjusted to avoid these is best method.
for the line count[i][j] = count[i-1][j]+count[i][j-1]+count[i-1][j-1]; there are some bugs in it. It should be count[i][j] = countPath(i-1, j)+countPath(i,j-1)+countPath(i-1, j-1);
The problem doesn't specify if it can go leftward or upward.
- da ye March 06, 2014