## Adobe Interview Question for Computer Scientists

Country: India
Interview Type: In-Person

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

(m + n -2) Choose (n-1). You are choosing (n-1) possible positions in the move sequence for the down movements, and the move sequence is (m+n-2) moves long.

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

This looks like a good solution. nCr could be written as nCn-r.
So (m+n-2)C (n-1) could also be written as (m+n-2)C(m-1).
So it could be vice versa

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

To be more precise, this is equal to:
(m + n - 2)! / (n - 1)!

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

its a permutation combination problem.....
with m-rows and n-columns.....the total number of steps to reach end point from start point is ((m-1)+(n-1)).......now the numbers of ways is actually the number of arrangements for this number of steps.....which is
!(m+n-2)/((!(m-1))*(!(n-1)))

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

@nihaldps, work a little on your presentation skills. Your question is not comprehensible at all.

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

|_13_|_4_|_1_|
|_09_|_3_|_1_|
|_03_|_2_|_1_|
|_01_|_1_|_0_|

For example, the array above has 13 paths from top-left corner to bottom-right corner. In each node, i have listed number of paths from that node to the bottom-right corner.

So, it can be seen easily it can be done in O(n^2) time.

Here is the sample code:

``````int A[m][n];
int i = m-1;
int j = n-1;
for(;i >= 0 && j >= 0; i--, j--)
{
if ( i == m-1 && j == n-1)
{
A[i][j] = 0;
}
else
{
A[i][j] = A[i+1][j] + A[i][j+1];
}

for (int k = i-1; k >= 0; k--)
A[k][j] = A[k+1][j+1];

for (int k = j-1; k >= 0; k--)
A[i][k] = A[i+1][k+1];
}``````

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

Sorry mistakes in code.
Here is corrected:

``````int A[m][n];
int i = m-1;
int j = n-1;
for(;i >= 0 && j >= 0; i--, j--)
{
if ( i == m-1 && j == n-1)
{
A[i][j] = 0;
}
else
{
A[i][j] = A[i+1][j] + A[i][j+1];
}

for (int k = i-1; k >= 0; k--)
{
if ( j == n-1)
{
A[k][j] = A[k+1][j];
}
else
{
A[k][j] = A[k+1][j] + A[k+1][j+1];
}
}

for (int k = j-1; k >= 0; k--)
{
if ( i == m-1)
{
A[i][k] = A[i][k+1];
}
else
{
A[i][k] = A[i][k+1] + A[i+1][k+1];
}
}
}``````

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

The answer is (m+n choose m) = (m+n choose n) since a path is isomorphic to an (m+n)-set consisting of m rightward and n downward moves. You can then calculate the binomial coefficients using Pascal's triangle recurrence in O((m+n)^2) time and O(m+n) space.

A more interesting version of this problem is to count paths between a source and a sink in an arbitrary directed acyclic graph.

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

This is incorrect. If the DAG is 3 X 3, then there are 5 paths.
o->o->o
| | |
v v v
o->o->o
| | |
v v v
o->o->o
(m+n choose n) would be (6 choose 3) = 20

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

@garmonbozia - you are right. The number of path for a 3x3 graph is - 5.
I think for a mxn the number of paths is - (m-1)+(n-1) and when the values of m and n are equal - it is (m+n-1). But I am not sure if this is correct answer.

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

if graph is 3x3 path is 6

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

psykotic's answer is almost right: it should be (m+n-2 choose n-1)

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

I was presented this question at Amazon, it was like this:

Given a 2D array, in how many ways you can go from cell (0, 0) to cell (m-1, n-1). The constraint is that you can only move below and right from a given cell. I solved it.

``````(m + n - 2) , if m = n
(m + n -1),  if m != n``````

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

even if m!=n
please explain in detail if i am wrong

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

I was asked the same question. Write a recursive program to compute the number of paths from top left to bottom right.

I couldn't write that time but later I tried at home and did it.

Here is the pseudo code:

{
return 0;

else
return 1;
}

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

You can do the below:
{
return 0;
else
}

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

isn't it the Catalan Number answer ?

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

Exactly 2 paths from diagonal node to other diagonal node.

Name 2 diagonal nodes as d1 and d2. We need to count number of paths from d1 to d2 through the binary tree rooted at d1.'
Think this way:
1) Imagine a binary tree rooted at d1. Its got one left child L and one right child, say R.
2) L again will have 2 children - left and right...(LL and LR) Same for the R => RL and RR.
3) Quickly enough now, note that out of LL and LR, only one path leads to d2. So, half the possibilities get eliminated at every breadth-wise walk down the tree.
4) Continuing this way down the L tree will yield only - and exactly - one path.
5) Continuing this way down the R tree will also ield exactly one more path.
=> 2 paths.

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

Solution:

Two movements are possible: down and right. (2)
Total no. of movements required: m+n-2 (regardless of path).

Answer is permutation of "down" and "right" for m+n-2 positions.
i.e. (m+n-2)P2.

For a 4x3 grid, no. of paths would be,
5P2 = 20

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

what about 3x3 grid ? Answer should be 12 according to you but its 6.

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

Solution:

Two movements are possible: down and right. (2)
Total no. of movements required: m+n-2 (regardless of path).

Answer is permutation of "down" and "right" for m+n-2 positions.
i.e. (m+n-2)P2.

For a 4x3 grid, no. of paths would be,
5P2 = 20

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

Solution:

Two movements are possible: down and right. (2)
Total no. of movements required: m+n-2 (regardless of path).

Answer is permutation of "down" and "right" for m+n-2 positions.
i.e. (m+n-2)P2.

For a 4x3 grid, no. of paths would be,
5P2 = 20

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

Solution:

Two movements are possible: down and right. (2)
Total no. of movements required: m+n-2 (regardless of path).

Answer is permutation of "down" and "right" for m+n-2 positions.
i.e. (m+n-2)P2.

For a 4x3 grid, no. of paths would be,
5P2 = 20

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

Solution:

Two movements are possible: down and right. (2)
Total no. of movements required: m+n-2 (regardless of path).

Answer is permutation of "down" and "right" for m+n-2 positions.
i.e. (m+n-2)P2.

For a 4x3 grid, no. of paths would be,
5P2 = 20

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

Solution:

Two movements are possible: down and right. (2)
Total no. of movements required: m+n-2 (regardless of path).

Answer is permutation of "down" and "right" for m+n-2 positions.
i.e. (m+n-2)P2.

For a 4x3 grid, no. of paths would be,
5P2 = 20

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

Solution:

Two movements are possible: down and right. (2)
Total no. of movements required: m+n-2 (regardless of path).

Answer is permutation of "down" and "right" for m+n-2 positions.
i.e. (m+n-2)P2.

For a 4x3 grid, no. of paths would be,
5P2 = 20

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

Solution:

Two movements are possible: down and right. (2)
Total no. of movements required: m+n-2 (regardless of path).

Answer is permutation of "down" and "right" for m+n-2 positions.
i.e. (m+n-2)P2.

For a 4x3 grid, no. of paths would be,
5P2 = 20

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.