Adobe Interview Question Computer Scientists
0of 0 votesGiven a graph (consider it to be a mxn grid). The nodes are node of a binary tree with left and right pointers. The start point (A) is at the left upper corner and the end point (B) is at right bottom corner. Each node points to its adjacent nodes in the grid (the right pointer points to the node on the right and the left points to the node just below it). The nodes at the lower and right edges will have child as null (right null for the right side edge and left null for the bottom edge). The end node at B is having both as null.
How many paths are possible which can lead you to B, if you start from A?
Country: India
Interview Type: In-Person
|_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];
}
}
}
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.
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.
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 on April 19, 2012 Edit | Flag Reply