Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
2
of 2 vote

Assume X=x2-x1 and Y=y2-y1 . Here x1 can be incremented by 1 and y1 can also incremented by 1. So there are X indentical small lengths ex.(x1+1,x1+1+1 etc) in horizontal direction to reach x2. similary in Y direction Y small lenghts to reach y2.. So this is like arranging X,Y idential units.and this can be done in (X+Y)!/X!Y!.

- bhupathi.chary May 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

correct

- shani May 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

according to this approach .. some invalid paths would also get included in the count.
like.

,
|      
|,_ _

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

its completely wrong,just check your method for x=y=1,2,3;
solution should be catalan number.

- sk June 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Anonymous: If you move two steps in x directions and 2 steps in y direction then you are definitely at (x+2,y+2). I think graphical representation makes you feel incorrect. But its actually correct.

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

@Sk: Can you please eloborate a bit more. I didnt get u r question

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

The answer is correct. And it's (X+Y)!/X!*Y!
For more info read about Pascal's triangle.

- sm.pavlenko February 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

#include <iostream>

using namespace std;

void find_paths(int x1, int y1, int x2, int y2, int &count)
{
    if(x1 > x2 || y1 > y2) return;
    if(x1 == x2 && y1 == y2){
        count++;
        return;
    }
    find_paths(x1+1, y1, x2, y2, count);
    find_paths(x1, y1+1, x2, y2, count);
}

int main()
{
    int count;
    int x1, y1, x2, y2;

    cin >> x1 >> y1 >> x2 >> y2;
    count = 0;
    find_paths(x1, y1, x2, y2, count);
    cout << count;

    return 0;
}

- Shubham Maheshwari June 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

correct.

- DeathEater August 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

let X=x2- x1
Y=y2-y1
Then to reach from (x1,y1) to (x2,y2) we need X+Y steps of which Y are of kind(0,+1) and X are of kind (+1,0) .Thus the total number of such paths is (X+Y) C X.

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

go thru the following answer it might help u:
anshulsalvo.blogspot.in/2012/01/problem-15.html

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

m=min(x2-x1,y2-y1);
n= max(x2-x1,y2-y1);
N(number of paths possible) = (n-m+2)pow(2,m) - 2;

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

1. there are (x2-x1) steps required to reach x2 (lets mark them all as X's. All X can be assumed identical, coz u cant arrange them among themselves)

2. there are (y2-y1) steps required to reach y2. (lets mark them all as Y's. All Y can be assumed identical, coz u cant arrange them among themselves)

Now both the steps are required to reach from (x1, y1) to (x2, y2)

Condition 1:
Remember that since u cant backtrack, so when u can take steps like from x1+1 to x1+2, you cant take step back from X1+2 to X1+1 .

Now all Xs can be arranged in 1 way among themselves. Now there are (X2-X1 +1) gaps between them. Within these gaps Ys can be places in (X2-X1 +1)! ways {Factorial of (X2-X1 +1 )}
hence, you can arrange X's.

Hence the answer.

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

max_no_path = pow ( 2, ( abs(x1-x2)* abs(y1-y2) )

explanation :
---->you pretty much are allowed to travel within a rectangle, where you can either go up or right ... you have 2 choices... thus pow(2, x)
---->the (x1-x2) * (y1-y2) are the decision nodes that create a new path

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

To make this work on some big grid and the distance is big (let's say you're trying to get from (0, 0) to (20, 20)), you can also use dynamic programming to speed things up.

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

To make this work on some big grid and the distance is big (let's say you're trying to get from (0, 0) to (20, 20)), you can also use dynamic programming to speed things up.

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

1. let M = x2-x1 and N = y2-y1.
2. from (x1, y1) you need M rights and N ups to reach the destination (x2, y2)
3. assume that M is 2 and N is 3, the path is a "multiset" (RRUUU). (R-move right, U-move up)
4. so the number of distinctive paths is the number of permutation of the multiset (RRUUU), which is 10.
RRUUU
RUUUR
URRUU
URUUR
:
:

5. in general, the answer is (M+N)!/(M!*N!)

- sqw May 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is another way of seeing the problem
Lets say you want to go from (0,0) to (3,3). Below are the observations
1. Any point (x,0) can only be reached in 1 way, where x <= 3
2. Any point (0,y) can also be reached in 1 way where y <= 3
3. Any other point (x,y) can be reached in number_of_ways_to_reach(x,y-1) + number_of_ways_to_reach(x-1,y).
Below function does the job

int get_num_paths(int x1, int y1, int x2, int y2) {  
  int **a;
  int m,n;
  m = x2 - x1+1;
  n = y2 - y1+1;
  /*Allocate a 2D array of size m*n */
  a = (int**)malloc((x2-x1)*sizeof(int*));
  for(int i=0; i<m; i++) {
    a[i] = (int*)calloc(n, sizeof(int));
  }
  a[0][0] = 1;
  for(int i=0; i<m; i++) {
    for(int j=0; j<n ; j++) {
      if(i==0) {
        a[i][j] = 1;
      } else {
        if(j==0) {
          a[i][j] = a[i-1][j];
        } else {
          a[i][j] = a[i][j-1] + a[i-1][j];
        }
      }
    }  /* end for */
  } /* end for */

  for(int i=0; i<m; i++) {
    for(int j=0; j<n ; j++) {
      cout << a[i][j] << " " ;
    }
    cout << endl;
  }
  return(a[m-1][n-1]);
}

The complexity is O(n^2) though..

- Prakash May 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int maxPaths(int x1, int x2, int y1, int y2) {
		
		if(x1 == x2 && y1 == y2)
			return 0;
		else if(x1 == x2 || y1 == y2)
			return 1;
		
		return maxPaths(x1, x2 - 1, y1, y2 - 1) + (x2 - x1) + (y2 - y1);
	}

- atul.bisaria May 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There was a mistake in my above solution. Here is the correct code:

public static int maxPaths(int x1, int x2, int y1, int y2) {
		
		if(x1 == x2 && y1 == y2)
			return 0;
		else if(x1 == x2 || y1 == y2)
			return 1;
		
		return 2 * maxPaths(x1, x2 - 1, y1, y2 - 1) + (x2 - x1) + (y2 - y1) - 2;
	}

- atul.bisaria May 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please elaborate the solution.

- Ghanshyam September 03, 2012 | Flag


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