Amazon Interview Question
SDE-2sCountry: India
Interview Type: Written Test
Let dx = |x1-x2| and dy = |y1-y2|
Case 1: M and S are the same point. Return 0.
Case 2: M and S are different points, but dx = dy. So M and S are on the same diagonal. Return 1.
Case 3: M and S are different points, but dx != dy. However, dx and dy are the same parity (both even or both odd). This means that M and S are on a square of the same colour (i.e. they are connected by diagonal moves). Since the grid is n x n, any two squares reachable by diagonal moves is reachable in a maximum of 2 diagonal moves. Return 2.
Case 4: None of the above, i.e. M and S are different points and dx and dy are of different parity (one is odd and one is even). Return infinity or the maximum integer.
Here is a java implementation:
public int minSteps(int n, int x1, int y1, int x2, int y2) {
int dx = Math.abs(x1-x2);
int dy = Math.abs(y1-y2);
int min = Integer.MAX_VALUE;
if (x1 == x2 && y1 == y2) {
min = 0;
} else if (dx == dy) {
min = 1;
} else if (dx % 2 == dy % 2) {
min = 2;
}
return min;
}
/* There are 4 cases for this problem:
* 1. S = M, then 0 move is needed;
* 2. M is on diagonal lines of S, then 1 move is needed;
* 3. M's diagonal lines have intersections with S's diagonal lines, then 2 moves are needed;
* 4. M can never reach S.
*
* Through analysis, we can get that this problem is actually to find the interactions.
* For any point on the board, we can get that the 2 diagonal lines are:
* a. y = x - (x0 - y0)
* b. y = -x + (x0 + y0), in which x0,y0 is the location of this point
*
* So now the problem can be simplified to that either of:
* a. the intersection of y = x - (x1 - y1) and y = -x + (x2 + y2) exists on the board
* its location is (x2 + y2 + x1 - y1) / 2, (x2 + y2 - x1 + y1) / 2
* b. the intersection of y = -x + (x1 + y1) and y = x - (x2 - y2) exists on the board
* its location is (x1 + y1 + x2 - y2) / 2, (x1 + y1 - x2 + y2) / 2
* */
static int findMoves(int length, Point s, Point m) {
if ((s.x == m.x) && (s.y == m.y)) {
return 0;
} else if ((m.y == m.x - (s.x - s.y)) || (m.y == -1 * m.x + (s.x + s.y))) {
return 1;
} else {
Point inter1 = new Point((s.x + s.y + m.x - m.y) / 2.0, (s.x + s.y - m.x + m.y) / 2.0);
Point inter2 = new Point((m.x + m.y + s.x - s.y) / 2.0, (m.x + m.y - s.x + s.y) / 2.0);
if (inter1.isOnBoard(length) || inter2.isOnBoard(length)) {
return 2;
} else {
return -1;
}
}
}
static class Point {
double x, y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
/* if coordinators are not integer or exceed limits, intersections are not on the board */
boolean isOnBoard(int length) {
if (x >= length || x < 0 || y >= length || y < 0) {
return false;
} else if (Math.floor(x) != x || Math.floor(y) != y) {
return false;
} else {
return true;
}
}
}
There could be 4 direction for M to move, for each direction the next point is:
lefttop: x2-1,y2+1; leftbottom:x2-1,y2-1;righttop:x2+1,y2+1;rightbottom:x2+1,y2-1, the difference between x2 and y2 can -2,+0, or +2.
So the strategy is :
1. check difference d2 = x2-y2, d1 = x1-y1
2. if (d2-d1)%2 != 0, then it is impossible, otherwise go #3
3. move righttop or rightbottom to make d2==d1, then move leftbottom or righttop to
make M to S
e.g:
when S = (10,3), M = (5,6)
then d1 = 10-3 = 7, d2 = 5-6=-1
cause d1-d2= 8, so move righttop 4 (=8/2) steps, then M is 9,2. after that, move righttop 1(=10-9) step
Considering four scenarios
1 ) S and M if two locations are same, then no need of moving
2 ) S and M either the x value is same for both or y value is same for both
then there is only one move needed ( it is a parallel or perpendicular points )
3 ) S and M is in perfect diagonal
then absolute value of S.x-M.x will be equal to S.y-M.y
Eg (1,7) and (6,2) is a perfect diagonal
4 ) rest all is 2 move - a diagonal move then a straight move, or vice versa
public int move(Point S, Point M) {
if (S.x == M.x && S.y == M.y) {
System.out.println("both are same point");
return 0;
} else if (S.x == M.x || S.y == M.y) {
System.out.println("it is a parallel or perpendicular points");
return 1;
} else if (Math.abs(S.x - M.x) == Math.abs(S.y - M.y)) {
System.out.println("it is in diagonal , return 1");
return 1;
} else
return 2;
}
Let dx = |x1-x2| and dy = |y1-y2|
Case 1: M and S are the same point. Return 0.
Case 2: M and S are different points, but dx = dy. So M and S are on the same diagonal. Return 1.
Case 3: M and S are different points, but dx != dy. However, dx and dy are the same parity (both even or both odd). This means that M and S are on a square of the same colour (i.e. they are connected by diagonal moves). Since the grid is n x n, any two squares reachable by diagonal moves is reachable in a maximum of 2 diagonal moves. Return 2.
Case 4: None of the above, i.e. M and S are different points and dx and dy are of different parity (one is odd and one is even). Return infinity or the maximum integer.
Here is a java implementation:
public int minSteps(int n, int x1, int y1, int x2, int y2) {
int dx = Math.abs(x1-x2);
int dy = Math.abs(y1-y2);
int min = Integer.MAX_VALUE;
if (x1 == x2 && y1 == y2) {
min = 0;
} else if (dx == dy) {
min = 1;
} else if (dx % 2 == dy % 2) {
min = 2;
}
return min;
}
There are four possibilities:
1- M and S are in the same position, o moves.
2- M and S are in the same diagonal, 1 move.
3- The diagonals projected by M and S intersect, 2 moves.
4- The diagonals projected by M and S do not intersect, 3 moves.
The idea is to see if the projected diagonals intersect, is to sum (x1 + x2) and (y1 + y2) if both numbers are even or odd the projected diagonals intersect and 2 moves are needed, other case a jump is needed given a total of 3 moves.
public int MinNumMoves(int x1, int y1, int x2, int y2)
{
//
if (x1 == x2 && y1 == y2)
return 0;
if (x1 + x2 == y1 + y2)
return 1;
bool evenx = ((x1 + x2) % 2) == 0;
bool eveny = ((y1 + y2) % 2) == 0;
return (evenx == eveny) ? 2 : 3;
}
import java.util.*;
- jay January 10, 2016public class BishopChess
{
private static int CheckCollide(int x1, int y1, int x2, int y2){
if(x1 < 0 || x2 < 0 || x1 > 7 || x2 > 7 ||y1 < 0 || y2 < 0 || y1 > 7 || y2 > 7)
{
System.out.println("Invalid place!!! Out of chess board");
return -1;
}
if((x1 + y1)%2 != (x2 + y2)%2)
{
System.out.println("Collision not possible");
return -1;
}
if((x1 + x2) == (y1 + y2) || (x1 - x2) == (y1 - y2))
{
//Direct hit possible
return 1;
}
else
return 2;
}
public static void main(String args[])
{
int x = 0;
int y = 0;
int m = 4;
int n = 6;
System.out.println("Optimal move: " + CheckCollide(/*x1,y1*/ x,y,/*x2, y2*/m,n));
}
}