Adobe Interview Question
Computer ScientistsCountry: 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