Facebook Interview Question Software Engineers
Country: United States
Interview Type: In-Person
Notice that not all points are accessible from point (x,y) = (1,1). In fact for a starting point (x,y) only points (m,n) such that gcd(m,n) == gcd(x,y) are accessible. In our example (m,n) = (4,4) can't be reached from (1,1). So the first step is understanding this. Once we have determined that the point is accessible we can preform simple calculations to figure out min steps to it.
Unless i'm not understanding the full constraints of the question, it would not make sense to do a BFS. Since it's in a matrix/grid and each move is either down or right and not diagonally, the min step should be a direct difference between the x and y coordinates in the classic translation fashion no? I believe the full details of the question needs to be flushed out.
int minStep(int x, int y){
int startX = 1;
int startY = 1;
steps = 0;
// Down
steps += y - startY;
// Right
steps += x - startX;
return steps;
}
int getMinSteps(int m, int n) {
if (m == 1 && n == 1)
return 0;
if (m == 1)
return n - m;
int p = n - m;
if (p < m) return (1 + getMinSteps(p, m));
return (1 + getMinSteps(m, p));
}
I think it can be a lot simpler, assuming from the example provided, the robot can increase any single coordinate arbitrarily in just one step. The function should return only 3 possible values: 0, 1 or 2 depending on the number of coordinates having the same value as the initial position. That is: 0 if position is (1,1), 1 if position is (1, any) or (any, 1) and 2 any other case. Of course we would add an error case if m or n are out of bounds.
Hi, are you sure 1) is right and 2) is down ? I think 1) is down and 2) is right . Please confirm.
public static int minSteps(int m, int n)
{
int steps = 0;
if(m<1 || n<1 || m==n)
return -1;
while((m!=1) || (n!=1))
{
if((m-n)>=1)
{
m = m-n;
++steps;
}
else if((n-m)>=1)
{
n= n-m;
++steps;
}
else if(m==n)
{
return -1;
}
}
return steps;
}
The shortest steps comes when moving diagonally meaning right-down-right-down... or down-right-down-right... . However, depending on m and n best answer may need to start from right or down. the easiest way is to do both and find the minimum. Here us my Java method:
public static int minSteps(int m, int n){
int x,y;
int stepsDownFirst=0;
boolean downDirection=true;
for(x=1, y=1;x<m || y<n;stepsDownFirst++){
if(downDirection)
y+=x;
else
x+=y;
downDirection=!downDirection;
}
int stepsRightFirst=0;
downDirection=false;
for(x=1, y=1;x<m || y<n;stepsRightFirst++){
if(downDirection)
y+=x;
else
x+=y;
downDirection=!downDirection;
}
if(stepsDownFirst<stepsRightFirst)
return stepsDownFirst;
else
return stepsRightFirst;
}
I realized there is away to make the code shorter and combine the two loops. This time I wrote it in C++ for my own practice:
int minSteps(int m, int n){
int x,y;
bool downDirection=true;
int steps=0;
for(x=y=1;(x<m||y<n)&&(x<n||y<m);steps++){
if (downDirection)
y+=x;
else
x+=y;
downDirection=!downDirection;
}
return steps;
}
The shortest path comes when you move diagonally. But depending on m and n you should either start with right or down. This is my Java method:
public static int minSteps(int m, int n){
int x,y;
int stepsDownFirst=0;
boolean downDirection=true;
for(x=1, y=1;x<m || y<n;stepsDownFirst++){
if(downDirection)
y+=x;
else
x+=y;
downDirection=!downDirection;
}
int stepsRightFirst=0;
downDirection=false;
for(x=1, y=1;x<m || y<n;stepsRightFirst++){
if(downDirection)
y+=x;
else
x+=y;
downDirection=!downDirection;
}
if(stepsDownFirst<stepsRightFirst)
return stepsDownFirst;
else
return stepsRightFirst;
}
The shortest path comes when you move diagonally. But depending on m and n you should either start with right or down. This is my Java method:
public static int minSteps(int m, int n){
int x,y;
int stepsDownFirst=0;
boolean downDirection=true;
for(x=1, y=1;x<m || y<n;stepsDownFirst++){
if(downDirection)
y+=x;
else
x+=y;
downDirection=!downDirection;
}
int stepsRightFirst=0;
downDirection=false;
for(x=1, y=1;x<m || y<n;stepsRightFirst++){
if(downDirection)
y+=x;
else
x+=y;
downDirection=!downDirection;
}
if(stepsDownFirst<stepsRightFirst)
return stepsDownFirst;
else
return stepsRightFirst;
}
public static int minSteps(int m, int n) {
// A(i, j) = A(i+j , i)
// A(i, j) = A(i , i+j)
int i = 1, j = 1;
int steps = 0;
while(i != m || j != n) {
if(canStepDown(m,n,i,j)) {
i += j;
} else {
j += i;
}
steps++;
System.out.println("Step " + steps + " :: i = " + i + " j = " + j );
}
return steps;
}
private static boolean canStepDown(int m, int n, int currM, int currN) {
int updatedM = currM + currN;
if(updatedM <= m && (n == currN || (updatedM + n) <= n)) {
return true;
}
return false;
}
public static int minSteps(int m, int n) {
// A(i, j) = A(i+j , i)
// A(i, j) = A(i , i+j)
int i = 1, j = 1;
int steps = 0;
while(i != m || j != n) {
if(canStepDown(m,n,i,j)) {
i += j;
} else {
j += i;
}
steps++;
System.out.println("Step " + steps + " :: i = " + i + " j = " + j );
}
return steps;
}
private static boolean canStepDown(int m, int n, int currM, int currN) {
int updatedM = currM + currN;
if(updatedM <= m && (n == currN || (updatedM + n) <= n)) {
return true;
}
return false;
}
public static int minSteps(int m, int n) {
// A(i, j) = A(i+j , i)
// A(i, j) = A(i , i+j)
int i = 1, j = 1;
int steps = 0;
while(i != m || j != n) {
if(canStepDown(m,n,i,j)) {
i += j;
} else {
j += i;
}
steps++;
System.out.println("Step " + steps + " :: i = " + i + " j = " + j );
}
return steps;
}
private static boolean canStepDown(int m, int n, int currM, int currN) {
int updatedM = currM + currN;
if(updatedM <= m && (n == currN || (updatedM + n) <= n)) {
return true;
}
return false;
}
public static int minSteps(int m, int n) {
// A(i, j) = A(i+j , i)
// A(i, j) = A(i , i+j)
int i = 1, j = 1;
int steps = 0;
while(i != m || j != n) {
if(canStepDown(m,n,i,j)) {
i += j;
} else {
j += i;
}
steps++;
System.out.println("Step " + steps + " :: i = " + i + " j = " + j );
}
return steps;
}
private static boolean canStepDown(int m, int n, int currM, int currN) {
int updatedM = currM + currN;
if(updatedM <= m && (n == currN || (updatedM + n) <= n)) {
return true;
}
return false;
}
This is the solution I tried with a helper method to check if I have to step down or right at any point of time.
public static int minSteps(int m, int n) {
// A(i, j) = A(i+j , i)
// A(i, j) = A(i , i+j)
int i = 1, j = 1;
int steps = 0;
while(i != m || j != n) {
if(canStepDown(m,n,i,j)) {
i += j;
} else {
j += i;
}
steps++;
System.out.println("Step " + steps + " :: i = " + i + " j = " + j );
}
return steps;
}
private static boolean canStepDown(int m, int n, int currM, int currN) {
int updatedM = currM + currN;
if(updatedM <= m && (n == currN || (updatedM + n) <= n)) {
return true;
}
return false;
}
Here is the code I tried. Adding a helper method to check if I have to step down or step right at each iteration
public static int minSteps(int m, int n) {
// A(i, j) = A(i+j , i)
// A(i, j) = A(i , i+j)
int i = 1, j = 1;
int steps = 0;
while(i != m || j != n) {
if(canStepDown(m,n,i,j)) {
i += j;
} else {
j += i;
}
steps++;
System.out.println("Step " + steps + " :: i = " + i + " j = " + j );
}
return steps;
}
private static boolean canStepDown(int m, int n, int currM, int currN) {
int updatedM = currM + currN;
if(updatedM <= m && (n == currN || (updatedM + n) <= n)) {
return true;
}
return false;
}
static int targetI = 3;
static int targetJ = 2;
public static int minimumSteps = targetI * targetJ;
public static void minSteps(int i, int j, int depth)
{
if(depth > minimumSteps)
{
return;
}
if(i == targetI && j== targetJ){
minimumSteps = depth;
System.out.println("Number of steps "+minimumSteps);
}
minSteps(i+j, j, depth+1);
minSteps(i, i+j, depth+1);
}
Instead of doing m := m - n; count + =1; thing we can do m := m - k * n, count += k; each step where k is either m/n if m % n > 0, or m/n -1 if the remainder == 0.
This algorithm is actually Euclid algorithm to find gdc(m, n). Very nice problem!
BTW guys, the m: = m - n solution and all recursion solutions have exponential (!) complexity. Yes, they require T = n steps, but the input is not an array of n numbers, but a single number n encoded with log n bits. So n = exp(log n).
E.g. is the input occupies 20 bits the number n itself could be as great as 2^20, and the algorithm could take as much time, e.g. if m == 1.
Here is the full algorithm:
int minSteps(int m, int n) {
if ((m < 1) | (n < 1)) {
return -1;
}
// rules are symmetric, let m be the greatest
if (m < n) {
int tmp = m;
m = n;
n = tmp;
}
int count = 0;
while (m != n) {
int k = ceil(m, n) - 1;
// let's do k steps back to (m - k *n, n)
int rem = m - k * n;
count += k;
// since rem <= n, let's swap horizontal and vertial positions to have (m >= n) again
m = n;
n = rem;
}
// m == n
if (m == 1) {
return count;
} else {
return -1; // m and n are not co-prime, cell (m, n) is not reachable from (1, 1)
}
}
int ceil(int m, int n) {
assert(m >= n);
assert(n >= 1);
int r = m % n;
if (r > 0) {
return m / n;
} else {
return m / n - 1;
}
}
The best algorithm to find shortest path in this case is BFS.
Start from (1,1), do BFS until reaching the goal.
C++ code (with bugs):
int minStep(int m, int n){
pair<int,int> Que[MMAX*NMAX];
int Dist[MMAX*NMAX];
bool Visited[MMAX][NMAX] = {false}; //bugs
Que[0] = make_pair(1,1);
Dist[0] = 0;
Visited[1][1] = true;
top = 0; last = 0;
while(top <= last){
pair<int,int> u = Que[top];
int x = u.first, y = u.second;
if (x==m and y==n) return Dist[top];
//right:
if (x+y<=m)
if (! Visited[x+y][y]){
last++;
Que[last] = make_pair(x+y,y);
Dist[last] = Dist[top]+1;
Visited[x+y][y] = true;
};
//down:
if (x+y<=n)
if (! Visited[x][x+y]){
last++;
Que[last] = make_pair(x,x+y);
Dist[last] = Dist[top]+1;
Visited[x][x+y] = true;
};
top++;
};
Return INFINITY; // Can't reach to the goal?
};
If I understood the question, the robot "cant" move in diagonal. Only down and right. If this is the case, and the question doesn't require one to find the actual path but to name the minimum number of steps, there is better than graph traversal. One can do this mathematically
(m-1) + (n-1) = min steps.
the reason is that it doesn't matter which path you take, you always need to move at least (m-1) vertically and (n-1) horizontally
I'm not sure I have understood this question. From my view, there is only one way to get to (m,n). If m>n, robot must come from (m-n,n). Otherwise comes from (m, n-m). So Here is my code:
- lydiahappycat March 09, 2015int minSteps(int m, int n) { if(m<1 || n <1) return -1; int count = 0; while(abs(m-n) && m>=1 && n>=1) { if(m>n) m=m-n; else n = n-m; count++; } if(m==1 && n==1) return count; else return -1; }