Amazon Interview Question for SDE-2s


Country: India
Interview Type: Written Test




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

import java.util.*;

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

- jay January 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Miraan Tabrez January 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

M can raech S only if both of them are in box of same colour.

And minimum steps will be 2.

Step 1: To locate M in line that is parallel to diagonal and containing S on it.

Step 2: To move ahead for reaching S.

- shubham January 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

M can only meet S if both of them are in same coloured boxes.

And there will be 2 minimum number of steps.

Step 1: To locate M in line which is parallel to diagonal and containing S on it.

Step 2: To move M ahead to reach S.

- shubham January 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

M can only meet S if both are in same coloured squares.

There will be 2 minimum steps.

Step 1: To locate M in line that is parallel to diagonal and containing S on it.

Step 2: To move M ahaed until it reaches S.

- shubham January 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* 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;
            }
        }
    }

- Yong.Christopher.Tang January 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- action0692 January 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- mail.shinev January 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Either I don't get something here, but it's always either 0 steps when coordinates are equal. 1 move when abs(x1-x2)=abs(y1-y2), and 2 moves in other cases.

- Alex January 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Miraan January 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

M can reach to S either in atmost 2 steps or may never reach. Latter occurs when they are on diff colors. In first case, it can reach to S directly or may take first step to get on line diagonal to S.

- vishalsahunitt January 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- hnatsu March 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

relocate the original from (0, 0) to fix point S(x1,y1), then the coordinate of M in the new coordinate system will be (x2-x1, y2-y1), let us say (x', y')

0. if x'=y'=0, no move.
1. if abs(x') = abs(y'), then one move
2. otherwise, two moves.

- Sean Locke April 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming S and M as 2 points:

if ((S.x == M.x) && (S.y == M.y)) //same spot
{
return 0;
}
elseif ( ((S.x+S.y)% 2) == ((M.x+M.y)%2)) // Sum of (x,y) be odd or even for S & M
{
If (Abs(S.x - S.y) == Abs (M.x - M.y)) // On the same diagonal
{ return 1;}
else
{ return 2;}
}
else
{
return 0;
}

- Nisheeth August 05, 2016 | Flag Reply


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