Microsoft Interview Question
Country: India
Interview Type: Written Test
From any starting point, there are two points one can reach. From each of those points, recurse. Invalid moves like going to the removed area or out of bounds should be skipped. Increment path counter everytime the point in consideration is the bottom right one.
This should work, anyone on how to get the complexity of this recursive solution?
what if use a table storing the the number of ways to reach the bottom right in each cell.
this is what i think.
=>dp[p-1,q-1]=0 cause we are already there.
=>start from the bottom right most index i.e, i=p-1,j=q-2 and traverse to wards the top left.
while(i>=0 && j>=0)
{
//traversing in the invalid region
if(i>=p-1-a && j<=b)
{ j--; continue;}
//if traversing in the edge cells of matrix after removing axb matrix
if(i==p-1-a && j<=b)
{dp[i][j]=dp[i+1][j]+1; if(j==0){i--; j=q-1;}else{j--;} continue; }
// if traversing in the non edge cells of matrix
if(i<p-1 && j<q-1)
{dp[i][j]=dp[i+1][j+1]+2}
// if traversing in the edge cells of the matrix
else if(i==p-1)
{dp[i][j]=dp[i][j+1]+1;}
else if(j==q-1)
{ dp[i][j]=dp[i+1][j]+1;}
if(j==0){i--; j=q-1;}else{j--;} }
}
//dp[0][0] holds the possible number of paths to bottom right corner.
let me know if there is a better way...
DP Solution
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace pathsinmesh
{
class Program
{
static void Main(string[] args)
{
int a = 1, b = 1;
int rows=2,cols=2;
rows++;//rows and columns are in terms of number of boxes. Converting them to edges
cols++;
int[,] arr=new int[rows,cols];
for (int i = 0; i < rows; i++)
{
for (int j = 0; j <cols; j++)
{
if (i < a && cols - j-1 < b)
{
arr[i, j] = -1;
}
else if (i == 0 || j == 0)
{
arr[i, j] = 1;
}
else
{
if (arr[i - 1, j] == -1)
{
arr[i, j] = arr[i, j - 1];
}
else
{
arr[i, j] = arr[i - 1, j] + arr[i, j - 1];
}
}
}
}
}
}
}
This looks a problem from the Khan Academy where you need to add the left and top possibilities current node's paths = left node's path+top node's path
(with a slight modification of a constraint )
The same rule applies here that the such that neither of the left, the right and the current node should be from the constraint areas.
1)If current node is in constraint area make its total path's to zero and skip the loop to start at next row (since all other nodes to the right will also be in restricted area)
2)Similarly if top node is in restricted area we should not add it, so an additional check on each of the current node's top child.
3)Lastly we need to check the left nodes for restricted area, or do we?From #1 we see that we will never have to encounter such a node.
(Assuming that we have loops from i to p and j to q)
We divide rectangle to 4 parts.
12
34
Part 2 is the removed section.
The paths consists of two parts: from top-left to the edge of part 1.
And from edge of part 3 to bot-right.
The total number should be sum (number of path in part 1 * corresponding number of path in part 2)
Path number in each parts should be able to calculated by combination number.
Then the time complexity will be roughly related to length of part 1 if factor calculation is cached.
Javascript DP solution
var m = [
[1,1,0],
[0,1,1],
[1,0,1]
];
var cutRows = 1, cutCols = 1;
function getNumberOfPaths(ri,ci){
var paths = 0;
if(ri<=cutRows - 1 && ci>=cols - cutCols)
return 0;
if(ri-1>=0) paths += m[ri-1][ci];
if(ci-1>=0) paths += m[ri][ci-1];
return paths;
}
var rows = m.length;
var cols = m[0].length;
m[0][0]=1;
for(var ri=0;ri<rows;ri++){
for(var ci=0;ci<cols;ci++){
if(ri===0 && ci===0) continue;
m[ri][ci] = getNumberOfPaths(ri,ci);
}
}
console.log(m[rows-1][cols-1]);
no of ways in original matrix P1: (p+q)!/(p!q!) [choosing from total p+q steps]
no of ways in sub matrix P2: (a+b)!(a!b!)
finally, in the reduced matrix: P1 - P2
This would only be true if all paths comprising P1 went through the top left and bottom right corner of the constraint region when they go through it at all (and couldn't come in through the sides), and if furthermore there were exactly one path in P1 having each forbidden path in P2 (there are many distinct paths in P1 that share a forbidden path in P2). Neither of these things is true in this problem.
Based on @eugene.yarovoi's way. I think we could get further answer.
if( a<p && b < q ){
return (p+q)!/(p!q!) - (a+b)!/(a!b!)
}else if(a == p && b < q){
return (p+q)!/(p!q!) - (p+q-b)!/(p!(q-b)!)
}else if( a < p && b == q){
return (p+q)!/(p!q!) - (p+q-1)!/(q!(p-a)!)
}else{
//remove all the matrix. We only have one left way.
return 1;
}
we can solve this through recursion, function f(x,y) starts with f(p-1,q-1). each time we run with f(x-1, y) & f(x, y-1). we run it until x & y are zero, when both are zero we increase the count+1.
to remove the matrix we check for is valid x & y.
pseudo code in java:
please let me know if I miss anything.
- Vijay M December 06, 2012