Microsoft Interview Question
Software Engineer / DevelopersTeam: Bing
Country: India
Interview Type: In-Person
let N(m,n) defines no. of ways to reach m,n from 0,0.
N(m-1,n-1) = N(m-2,n-1) + N(m-1,n-2) + 2;
TO N.A
u said this.......
N(m-1,n-1) = N(m-2,n-1) + N(m-1,n-2) + 2;
the addition of 2 is not required,bcoz sum of paths is just N(m-2,n-1) + N(m-1,n-2) as,i think it will be just
am i right???/
Get the number of paths to a box is the sum of the number of paths to the box above and the box to the left. This is equivalent to pascal's triangle rotated 45 degrees left.
To get the coordinates of the (m,n) box in terms of the triangle you will be in the m+n-2 row (starting at 0) and the nth number in that row.
This is m+n-2 choose n,
The equation for the solution is:
(m+n-2)! / ((m-2)! * n!)
int NumWaysStartToEnd(bool arr[M+1][N+1], int row, int col)
{
static int counter = 0;
if(row > M || col > N) return 0;
if(row == M && col == N) counter++;
NumWaysStartToEnd(arr, row+1, col);
NumWaysStartToEnd(arr, row, col+1);
return counter;
}
//Usage:
bool boolArr[M+1][N+1] = {
{0,0,0,0},
{0,0,0,0},
{0,0,0,0},
{0,0,0,0},
{0,0,0,0}
};
cout << NumWaysStartToEnd(boolArr, 0, 0);
The following method uses dynamic programming:-
int countways(int m,int n)
{ int count[100][100],i,j; //assuming m<=100 and n<=100
for(j=0;j<n;i++)
count[m-1][i]=1;
for(i=0;i<m;j++)
count[i][n-1]=1;
for(i=m-2;i>=0;i--)
for(j=n-2;j>=0;j--)
count[i][j]=count[i+1][j]+count[i][j+1];
return count[0][0];
}
The basic idea is that, from either last row or last column, there is only one way for him to reach the endpoint. From any other point, the number of ways in which he can reach end point is equal to sum of number of ways in which he can reach end point by moving right and moving down...
Now, using this idea, if someone can arrive at a better mathematical formula, it would yield greater results.
Let us do it this way. Say, we know that for a 3X3, the number of ways to traverse is 6, for 3X2, it is 3, and for 3X1, it is 1. Now, when we change it to 4X3, the number of paths would be sum of all these three, which is 10, because you move right and then it is a 3X3 matrix, then you move down and right, it is a 3X2 matrix, then down, down and right, and it is a 3X1 matrix. Similarly, for 4X4, it would be N(4X3)+N(3X3)+N(2X3)+N(1X3), which is 20, and so on.
Translating it into code,
//call the function as countpaths(0,0) for m,n matrix
function countpaths(x,y)
{
int j=y,count=0;
for (i=x;i<m;i++)
{
if ((i==m-1) && (j==n-2)) || ((i==m-2) && (j=n-1))
return count + 1;
if (j < n-1)
count =count + countpaths(i,j+1);
}
}
May be you can save some redundant calculations using dynamic programming.
use a count[][] matrix to store the count from the (i,j) you have already visited. That way you are using the solutions for smaller problems without solving them repeatedly.
Backtrackng Algorithm
If destination is reached
print the solution matrix
Else
a) Mark current cell in solution matrix as 1.
b) Move forward in horizontal direction and recursively check if this
move leads to a solution.
c) If the move chosen in the above step doesn't lead to a solution
then move down and check if this move leads to a solution.
d) If none of the above solutions work then unmark this cell as 0
(BACKTRACK) and return false.
He needs to take total 'm-1 down' + 'n-1 right' steps
- CodeMyCode December 17, 2011Its classical Permutation and Combination problem.
Refer to theorem 3 on this page intmath.com/counting-probability/3-permutations.php
Hence ans = (m+n-2)! / ((m-1)!*(n-1)!)