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.

- Anonymous April 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Punit Jain May 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Thomas February 15, 2014 | Flag
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)))

- chandanbaranwal May 04, 2012 | Flag Reply
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.

- Anonymous February 21, 2012 | Flag Reply
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];
}

- gimli February 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gimli February 21, 2012 | Flag
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.

- psykotic February 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 February 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nihaldps February 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if graph is 3x3 path is 6

- Anonymous February 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- alexmexmat September 06, 2013 | Flag
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.

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.

- mag February 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

even if m!=n
answer should be m+n-2
please explain in detail if i am wrong

- asdfgh April 21, 2012 | Flag
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:

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

- Punit Jain May 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can do the below:
int Number_of_Paths (node *head)
{
if (!head)
return 0;
else
return (1+ Number_of_Paths(head->right) + Number_of_Paths(head->down));
}

- code_guru May 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

isn't it the Catalan Number answer ?

- villagemonkey June 03, 2012 | Flag Reply
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.

- Nix February 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous February 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Punit Jain May 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous February 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous February 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous February 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous February 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous February 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous February 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous February 26, 2012 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More