Microsoft Interview Question for Software Engineer / Developers


Team: Bing
Country: India
Interview Type: In-Person




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

He needs to take total 'm-1 down' + 'n-1 right' steps
Its 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)!)

- CodeMyCode December 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is a correct argument

- Anonymous December 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

- N.A. December 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

(m-2)*2 + (n-2)*2 +2

- sanjay.2812 December 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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???/

- abhishek December 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No Need to add 2 in that code

- Jey April 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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!)

- Sean December 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

(m+n)! / (m!.n!)

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

Let n = 3, m = 3; Number of ways is 6. In your solution it is 20.
The way to do it is (m + n - 2)! / (m-1)!(n-1)! if n, m > 1. If not, the answer is 1

- Alex Fetisov December 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Samujjal December 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is the need of using array??
we can do this without using array naah...

- gauravsingh.nit.jsr December 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

The solution can be generated by looking at the fact that we have to travel total of m-1 distance to right and n-1 distance downwards. So we have total of m+n-2 steps. Now out of these we need to select the m-1 towards right steps which can be done in m+n-2Cm-1 ways. :)

- Srikant Aggarwal December 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- anoopananth December 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There are m-1 ways to go right (for 0..m-1 counting) and n-2 ways to go down (counting 0 to n-1). So possible ways is (m-1) * (n-2). I tested this with few simple metrices.

- Shriyal Padte January 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- tallitester January 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous February 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if we have a square matrix like 4X4..will we be able to follow the same pattern..are we supposed to do like 4X3 then 4X2 then 4..?

- sharath_bcs10@nitc.ac.in September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Ganesh Deo July 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

et 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) + N(m-2, n-2);

- ram January 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For a mXn matrix,

If(n==1) then noOfPaths = 1
else
noOfPaths = [(m*n*2)-m-n]-(m*n)+2 -> Cyclomatic complexity of a connected graph

- Prasant Sutaria September 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Suppose I have to move from 1,1 to bottom right of the matrix of 10*10 size i.e from 1,1 to 10,10 and we have to avoid certain points such as 5,5 and 2,2 means that i can not go from 5,5 and 2,2. how do we do that??

- Asmit Vimal April 23, 2020 | Flag Reply


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