## Adobe Interview Question Computer Scientists

• 0

Given 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

Comment hidden because of low score. Click to expand.
5
of 5 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.
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

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

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.
-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 walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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