## Microsoft Interview Question

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
3
of 3 vote

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:

``````//run f(p-1,q-1);
//static int count = 0;

void f(x,y){
if(x==0 && y ==0){
count++;
}else if(isValidX(x) || isValidY(y)){
f(x-1,y);f(x,y-1);
}
}

Boolean  isValidX(x){
if(x>0 && x>(p-a-1))
return true;

return false;
}

Boolean  isValidY(y){
if(y>0 && x<(q-b-1))
return true;

return false;
}``````

please let me know if I miss anything.

Comment hidden because of low score. Click to expand.
2
of 4 vote

A typical DP problem. Recursion will be slow as you will be traversing same path multiple times.

Comment hidden because of low score. Click to expand.
0
of 2 vote

this is problem of a running contest.

Comment hidden because of low score. Click to expand.
0

Catch it before it runs away!

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0

The complexity of the naive recursive algorithm is exponential in the size of the grid. When using dynamic programming, the complexity will be linear in the total number of locations in the grid.

Comment hidden because of low score. Click to expand.
0
of 0 vote

dynamic programming with contraints:
for each cell keep the number of paths from top left corner to that cell not violating contraints. The answer would be in the bottom right cell of dp table. Time/Space complexity O(pXq)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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];
}
}
}
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

For unsliced matrix you have (p+q)Cp or (p+q)Cq ways. But as there are some paths cut off due to slicing of a*b sub matrix, it will be (p+q)Cp - sum((m+n-x)C(m-x)) when x>0 + 1

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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;
}``````

Comment hidden because of low score. Click to expand.
0

@kevin: no, that's not right.

Comment hidden because of low score. Click to expand.
0

@eugene.yarovoi , why???
You need to give a counter example, please.

Comment hidden because of low score. Click to expand.
0

I just don't see any reason why it would be right. You haven't indicated any reasoning for your answer. The burden of proof is on the person proposing the solution to give an argument for why it's correct.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.