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.

- Vijay M December 06, 2012 | Flag Reply
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.

- Arunava December 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

this is problem of a running contest.

- Anonymous December 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Catch it before it runs away!

- Anonymous September 19, 2013 | Flag
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?

- Metta December 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi December 06, 2012 | Flag
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)

- aste December 07, 2012 | Flag Reply
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...

- rajesh December 07, 2012 | Flag Reply
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];
                        }
                    }
                }
            }
        }
    }
}

- WarriorOfLight December 07, 2012 | Flag Reply
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)

- Ashar December 07, 2012 | Flag Reply
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.

- Anonymous December 19, 2012 | Flag Reply
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]);

- S.Abakumoff December 24, 2012 | Flag Reply
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

- Riyad Parvez December 28, 2012 | Flag Reply
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

- Imon December 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi December 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kevin March 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@kevin: no, that's not right.

- eugene.yarovoi March 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kevin March 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi March 10, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More