Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
according to this approach .. some invalid paths would also get included in the count.
like.
,
|
|,_ _
its completely wrong,just check your method for x=y=1,2,3;
solution should be catalan number.
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.
#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;
}
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.
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!)
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..
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);
}
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;
}
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