## Amazon Interview Question for Software Engineer / Developers

• 0

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

Comment hidden because of low score. Click to expand.
0

correct

Comment hidden because of low score. Click to expand.
0

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

``````,
|
|,_ _``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

The answer is correct. And it's (X+Y)!/X!*Y!

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

Comment hidden because of low score. Click to expand.
0

correct.

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.

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

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;

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.

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

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.

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.

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!)

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Could you please elaborate the solution.

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.

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