Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




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

Ok Here is the logic:

1. Create two trees one with the starting position of the knight as the root node and the other as the ending position of the knight as to root node.

2. The tree is such that for any Node N, all its children can be reached by a single move of the knight. So if N can be represented by n(x,y) then the child nodes would be n(x+1,y+2),n(x+1,y-2), n(x-1,y+2), n(x-1,y-2), n(x+2,y+1), n(x+2,y-1), n(x-2,y+1), n(x-2,y-1)

3. Now intersection of the two trees with the least number of stems will provide you the answer.

PS: all positions can ultimately be reached by the knight. The challenge is finding the shortest way.

- enoughtworldisnot September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

someone pls suggest some solution

- TTB September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about using A* search where the position cost would be the number of moves needed to get to the solution and the expected remaining cost off ( | pos_x - dest_x | + | pos_y - dest_y | ) / 3 . Computing the memory cost and the O would be hard though...

- Anonymous September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A* seems a good solution. We normally construct a A* tree from a graph, but here we can construct it directly from the chessboard.
I did not get why the remaining cost (i.e. the heuristic) is calculated as done. I think it should be straight-line distance.

- nharryp November 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also, for a chessboard of infinite size, what will be the modification?

- nharryp November 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do a BFS on the possible moves and the first point which hits destionation is the answer. Knight can move from nay point to any point, which can be shown by creating a set of moves which move the knight to the next square and generalizing from there.

- Anonymous September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static Scanner s=new Scanner(System.in);
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int sx,sy,dx,dy;
sx=s.nextInt();
sy=s.nextInt();
dx=s.nextInt();
dy=s.nextInt();
int mx=0,my=0;
int vertmoves,horzmoves;
vertmoves=dy-sy;
horzmoves=dx-sx;
if(Math.abs(vertmoves)>Math.abs(horzmoves))
{
if(vertmoves<0 && horzmoves>0)
{
while(horzmoves!=mx && vertmoves!=my && (dx!=sx && dy!=sy ))
{
my-=2;
my+=1;
}
if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
else if(vertmoves>0 && horzmoves>0)
{
while(horzmoves!=mx && vertmoves!=my &&(dx!=sx && dy!=sy ))
{
mx+=2;
my+=1;
}
if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
else if(vertmoves<0 && horzmoves<0)
{
while((horzmoves)!=mx && (vertmoves)!=my && (dx!=sx && dy!=sy ))
{
mx-=2;
my-=1;
}
if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
else if(vertmoves<0 && horzmoves<0)
{
while((horzmoves)!=mx && (vertmoves)!=my && (dx!=sx && dy!=sy ))
{
mx+=2;
my-=1;
}
if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
}
else if(Math.abs(vertmoves)<Math.abs(horzmoves))
{
if(vertmoves<0 && horzmoves>0)
{
while(horzmoves!=mx && (vertmoves)!=my && (dx!=sx && dy!=sy ))
{
my-=1;
mx+=2;
}
if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
else if(vertmoves>0 && horzmoves>0)
{
while((horzmoves!=mx && vertmoves!=my) && (dx!=sx && dy!=sy ))
{
my+=1;
mx+=2;
}
if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
else if(vertmoves<0 && horzmoves<0)
{
while((horzmoves)!=mx && (vertmoves)!=my && (dx!=sx && dy!=sy ))
{
my-=1;
mx-=2;
}
else if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
else if(vertmoves>0 && horzmoves<0)
{
while((horzmoves)!=mx && vertmoves!=my && (dx!=sx && dy!=sy ))
{
my+=1;
mx-=2;
}
if(dx==sx && dy==sy)
System.out.println("can move");
else
System.out.println("cant move");
}
}
}
}

- vee* September 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It seems like a graph with 64 nodes. Any two nodes are connected if there is one step movement between them. You can create that easyly. Then to find the shortest path just apply Dijkstra algorithm.

- max September 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To get the knight from <x0,y0> to <x1,y1>, you have to find an all-integers solution to the system
c0<2,1>+c1<-2,1>+c2<-2,-1>+c3<2,-1>+c4<1,2>+c5<-1,2>+c6<1,-2>+c7<-1,-2>+<x0,y0> = <x1, y1>

(You can dump half the terms, since for example c0<2,1>+c2<-2,-1>=(c0-c2)<2,1>.)

This is basic linear algebra, will take a bit of playing around but it's doable. The shortest route would correspond to the smallest-norm solution.

Pathfinding or the brute-force traversing of the entire state-space of possible moves will also work. But solving the equation above is probably the most optimal approach? Any other opinions?

- mathytime September 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my answer.

from collections import deque


def in_bounds(x, y, xb, yb):
    return x <= xb and y <= yb


def movements(x, y, mov):
    return [(x - 1, y - 2, mov), 
            (x + 1, y - 2, mov), 
            (x - 2, y - 1, mov), 
            (x + 2, y - 1, mov), 
            (x - 2, y + 1, mov), 
            (x + 2, y + 1, mov), 
            (x - 1, y + 2, mov), 
            (x + 1, y + 2, mov)]

def filter (list, xbounds, ybounds):
    return [i for i in list if i[0] <= xbounds and i[1] <= ybounds and i[0] >= 0 and i[1] >= 0]


def shorter_path(x, y, xtarget, ytarget, xbounds, ybounds):
    visited = dict()
    queue = deque()
    queue.append((x, y, 0))

    while (len(queue) > 0):
        current = queue.popleft()

        if (current[0] == xtarget and current[1] == ytarget): return current[2] 
        if visited.has_key((current[0], current[1])): continue

        visited[(current[0], current[1])] = True

        movs = movements(current[0], current[1], current[2] + 1)
        movs = filter(movs, xbounds, ybounds)
        queue.extend(movs)

    return -1

#Entry
print shorter_path(0, 0, 4, 4, 8, 8)

- daniel September 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Solution {

class Point
{
private int x, y;

public Point()
{}

public Point(int x1, int y1)
{
this.x = x1;
this.y = y1;
}
}

class GraphNode {
private Point point;

public GraphNode(Point p)
{ this.point = p;

}
}

int[][] chessBoard;

public int knight(int N, int M, int x1, int y1, int x2, int y2) {

chessBoard = new int[N][M];

Point s = new Point(x1-1,y1-1);

int res =0;

GraphNode start = new GraphNode(s);

Queue<GraphNode> q = new LinkedList<GraphNode>();

q.add(start);
q.add(null);


while(!q.isEmpty()){
GraphNode cur = q.poll();

if(cur==null)
{
if(!q.isEmpty())
q.add(null);

res++;
}

else
{
Point p = cur.point;

if(p.x == x2-1 && p.y==y2-1)
return res;

chessBoard[p.x][p.y]=-1;

Point[] moves = PossibleJumps(p,N,M);

for(int i=0;i<moves.length;i++)
{
q.add(new GraphNode(moves[i]));
}
}

}

return -1;
}



public Point[] PossibleJumps(Point P, int N, int M)
{
ArrayList<Integer> xArray = new ArrayList<Integer>();
ArrayList<Integer> yArray = new ArrayList<Integer>();
//Point 1
if (P.x - 1 >= 0 && P.y + 2 <= M-1)
{
if (chessBoard[P.x - 1][P.y + 2] != -1)
{
xArray.add((int)(P.x - 1));
yArray.add((int)(P.y + 2));
chessBoard[P.x - 1][P.y + 2] = -1;
}
}
//Point 2
if (P.x + 1 <= N-1 && P.y + 2 <= M-1)
{
if (chessBoard[P.x + 1][P.y + 2] != -1)
{
xArray.add((int)(P.x + 1));
yArray.add((int)(P.y + 2));
chessBoard[P.x + 1][P.y + 2] = -1;
}
}
//Point 3
if (P.x + 2 <= N-1 && P.y + 1 <= M-1)
{
if (chessBoard[P.x + 2][P.y + 1] != -1)
{
xArray.add((int)(P.x + 2));
yArray.add((int)(P.y + 1));
chessBoard[P.x + 2][P.y + 1] = -1;
}
}
//Point 4
if (P.x + 2 <= N-1 && P.y - 1 >= 0)
{
if (chessBoard[P.x + 2][P.y - 1] != -1)
{
xArray.add((int)(P.x + 2));
yArray.add((int)(P.y - 1));
chessBoard[P.x + 2][P.y - 1] = -1;
}
}
//Point 5
if (P.x + 1 <= N-1 && P.y - 2 >= 0)
{
if (chessBoard[P.x + 1][P.y - 2] != -1)
{
xArray.add((int)(P.x + 1));
yArray.add((int)(P.y - 2));
chessBoard[P.x + 1][P.y - 2] = -1;
}
}
//Point 6
if (P.x - 1 >= 0 && P.y - 2 >= 0)
{
if (chessBoard[P.x - 1][P.y - 2] != -1)
{
xArray.add((int)(P.x - 1));
yArray.add((int)(P.y - 2));
chessBoard[P.x - 1][P.y - 2] = -1;
}
}
//Point 7
if (P.x - 2 >= 0 && P.y - 1 >= 0)
{
if (chessBoard[P.x - 2][P.y - 1] != -1)
{
xArray.add((int)(P.x - 2));
yArray.add((int)(P.y - 1));
chessBoard[P.x - 2][P.y - 1] = -1;
}
}
//Point 8
if (P.x - 2 >= 0 && P.y + 1 <= M-1)
{
if (chessBoard[P.x - 2][P.y + 1] != -1)
{
xArray.add((int)(P.x - 2));
yArray.add((int)(P.y + 1));
chessBoard[P.x - 2][P.y + 1] = -1;
}
}
Point[] pArray = new Point[xArray.size()];
for (int i = 0; i < pArray.length; i++)
{
pArray[i] = new Point((int)xArray.get(i), (int)yArray.get(i));

}
return pArray;
}


}

- Somnath Asati September 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Solution {

class Point
{
private int x, y;

public Point()
{}

public Point(int x1, int y1)
{
this.x = x1;
this.y = y1;
}
}

class GraphNode {
private Point point;

public GraphNode(Point p)
{ this.point = p;

}
}

int[][] chessBoard;

public int knight(int N, int M, int x1, int y1, int x2, int y2) {

chessBoard = new int[N][M];

Point s = new Point(x1-1,y1-1);

int res =0;

GraphNode start = new GraphNode(s);

Queue<GraphNode> q = new LinkedList<GraphNode>();

q.add(start);
q.add(null);


while(!q.isEmpty()){
GraphNode cur = q.poll();

if(cur==null)
{
if(!q.isEmpty())
q.add(null);

res++;
}

else
{
Point p = cur.point;

if(p.x == x2-1 && p.y==y2-1)
return res;

chessBoard[p.x][p.y]=-1;

Point[] moves = PossibleJumps(p,N,M);

for(int i=0;i<moves.length;i++)
{
q.add(new GraphNode(moves[i]));
}
}

}

return -1;
}



public Point[] PossibleJumps(Point P, int N, int M)
{
ArrayList<Integer> xArray = new ArrayList<Integer>();
ArrayList<Integer> yArray = new ArrayList<Integer>();
//Point 1
if (P.x - 1 >= 0 && P.y + 2 <= M-1)
{
if (chessBoard[P.x - 1][P.y + 2] != -1)
{
xArray.add((int)(P.x - 1));
yArray.add((int)(P.y + 2));
chessBoard[P.x - 1][P.y + 2] = -1;
}
}
//Point 2
if (P.x + 1 <= N-1 && P.y + 2 <= M-1)
{
if (chessBoard[P.x + 1][P.y + 2] != -1)
{
xArray.add((int)(P.x + 1));
yArray.add((int)(P.y + 2));
chessBoard[P.x + 1][P.y + 2] = -1;
}
}
//Point 3
if (P.x + 2 <= N-1 && P.y + 1 <= M-1)
{
if (chessBoard[P.x + 2][P.y + 1] != -1)
{
xArray.add((int)(P.x + 2));
yArray.add((int)(P.y + 1));
chessBoard[P.x + 2][P.y + 1] = -1;
}
}
//Point 4
if (P.x + 2 <= N-1 && P.y - 1 >= 0)
{
if (chessBoard[P.x + 2][P.y - 1] != -1)
{
xArray.add((int)(P.x + 2));
yArray.add((int)(P.y - 1));
chessBoard[P.x + 2][P.y - 1] = -1;
}
}
//Point 5
if (P.x + 1 <= N-1 && P.y - 2 >= 0)
{
if (chessBoard[P.x + 1][P.y - 2] != -1)
{
xArray.add((int)(P.x + 1));
yArray.add((int)(P.y - 2));
chessBoard[P.x + 1][P.y - 2] = -1;
}
}
//Point 6
if (P.x - 1 >= 0 && P.y - 2 >= 0)
{
if (chessBoard[P.x - 1][P.y - 2] != -1)
{
xArray.add((int)(P.x - 1));
yArray.add((int)(P.y - 2));
chessBoard[P.x - 1][P.y - 2] = -1;
}
}
//Point 7
if (P.x - 2 >= 0 && P.y - 1 >= 0)
{
if (chessBoard[P.x - 2][P.y - 1] != -1)
{
xArray.add((int)(P.x - 2));
yArray.add((int)(P.y - 1));
chessBoard[P.x - 2][P.y - 1] = -1;
}
}
//Point 8
if (P.x - 2 >= 0 && P.y + 1 <= M-1)
{
if (chessBoard[P.x - 2][P.y + 1] != -1)
{
xArray.add((int)(P.x - 2));
yArray.add((int)(P.y + 1));
chessBoard[P.x - 2][P.y + 1] = -1;
}
}
Point[] pArray = new Point[xArray.size()];
for (int i = 0; i < pArray.length; i++)
{
pArray[i] = new Point((int)xArray.get(i), (int)yArray.get(i));

}
return pArray;
}
}

- Somnath Asati September 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

/**
 * Created by ugurdonmez on 12/09/16.
 */
public class Solution {

    public static void main(String [] args) {

        System.out.println(knight(2,20,1,18,1,5));

    }

    public static int knight(int N, int M, int x1, int y1, int x2, int y2) {

        Map<Integer, BoardArea> map = new HashMap<>();

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                map.put(i * M + j, new BoardArea(i,j));
            }
        }

        int key1 = x1 * M + y1;
        int key2 = x2 * M + y2;

        return getKnightMinMove(map.get(x1 * M + y1), map.get(x2 * M + y2), N, M, map);
    }

    public static int getKnightMinMove(BoardArea pos1, BoardArea pos2, int n, int m, Map<Integer, BoardArea> map) {

        PriorityQueue<QueueWrapper> queue = new PriorityQueue<>();
        Set<BoardArea> visited = new HashSet<>();

        queue.add(new QueueWrapper(pos1, 0));

        while (!queue.isEmpty()) {

            QueueWrapper queueWrapper = queue.poll();
            BoardArea boardArea = queueWrapper.boardArea;

            if (boardArea.equals(pos2)) {
                return queueWrapper.length;
            }

            if (!visited.contains(boardArea)) {
                // add connections
                if (boardArea.x + 2 <= n) {
                    if (boardArea.y - 1 >= 1) {
                        queue.add(new QueueWrapper(map.get((boardArea.x + 2) * m + boardArea.y - 1), queueWrapper.length+1));
                    }

                    if (boardArea.y + 1 <= m) {
                        queue.add(new QueueWrapper(map.get((boardArea.x + 2) * m + boardArea.y + 1), queueWrapper.length+1));
                    }
                }

                if (boardArea.x + 1 <= n) {
                    if (boardArea.y - 2 >= 1) {
                        queue.add(new QueueWrapper(map.get((boardArea.x + 1) * m + boardArea.y - 2), queueWrapper.length+1));
                    }

                    if (boardArea.y + 2 <= m) {
                        queue.add(new QueueWrapper(map.get((boardArea.x + 1) * m + boardArea.y + 2), queueWrapper.length+1));
                    }
                }

                if (boardArea.x - 2 >= 1) {
                    if (boardArea.y - 1 >= 1) {
                        queue.add(new QueueWrapper(map.get((boardArea.x - 2) * m + boardArea.y - 1), queueWrapper.length+1));
                    }

                    if (boardArea.y + 1 <= m) {
                        queue.add(new QueueWrapper(map.get((boardArea.x - 2) * m + boardArea.y + 1), queueWrapper.length+1));
                    }
                }

                if (boardArea.x - 1 >= 1) {
                    if (boardArea.y - 2 >= 1) {
                        queue.add(new QueueWrapper(map.get((boardArea.x - 1) * m + boardArea.y - 2), queueWrapper.length+1));
                    }

                    if (boardArea.y + 2 <= m) {
                        queue.add(new QueueWrapper(map.get((boardArea.x - 1) * m + boardArea.y + 2), queueWrapper.length+1));
                    }
                }

                visited.add(boardArea);
            }
        }

        return -1;
    }
}

class BoardArea {

    final int x;
    final int y;

    public BoardArea(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        BoardArea boardArea = (BoardArea) o;

        if (x != boardArea.x) return false;
        return y == boardArea.y;
    }

    @Override
    public int hashCode() {
        int result = x;
        result = 31 * result + y;
        return result;
    }
}


class QueueWrapper implements Comparable<QueueWrapper>{

    final BoardArea boardArea;
    final int length;

    public QueueWrapper(BoardArea boardArea, int length) {
        this.boardArea = boardArea;
        this.length = length;
    }

    @Override
    public int compareTo(QueueWrapper o) {
        return Integer.compare(this.length, o.length);
    }
}

- ugurdonmez87 September 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

On a chess board a knight can only go diagonal or forward direction.

- TTB September 09, 2014 | 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