Adobe Interview Question Computer Scientists

  • adobe-interview-questions
    0
    of 0 votes
    27
    Answers

    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?

    - nihaldps on February 21, 2012 in India Report Duplicate | Flag
    Adobe Computer Scientist Trees and Graphs

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.

- Anonymous on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on 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 on February 26, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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