## Adobe Interview Question

Computer Scientists**Country:**India

**Interview Type:**In-Person

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

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

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

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.

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

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

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.

The answer:

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

@nihaldps: Your answer in comments is correct. But you original question doesn't mention the constraint.

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:

int Number_of_Paths (node *head)

{

if (!head)

return 0;

if (head->right && head->down)

return ( Number_of_Paths(head->right) + Number_of_Paths(head->down));

else if (head->right)

return Number_of_Paths (head->right);

else if (head->down)

return Number_of_Paths (head->down);

else

return 1;

}

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.

Answer: (m+n-2)P2.

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

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

- Anonymous April 19, 2012