Question

GoldMan Sachs | Recent Interview Experiences (Phone Screening) | Coderpad | SDE | Set-25

Answer 1

I just got the below question in GS phone screening round:

 

You are given a NXN chessboard. Find if it is possible to reach a point (m,n) starting from (p,q) USING ONLY KNIGHT MOVES.

 

Follow Up : Find MINIMUM number of moves to do so.

 

Can anyone explain how to approach this problem ? Interviewer wanted to avoid using graphs to solve this.

 

Thanks

Answer 2

class Cell{
    // x, y represents chessboard coordinates
    // dist represents its minimum distance from the source
    int x, y, dist;
    public Cell(int x, int y){
        this.x = x;
        this.y = y;
    }
    public Cell(int x, int y, int dist){
        this.x = x;
        this.y = y;
        this.dist = dist;
    }
}
private int[] row = { 2, 2, -2, -2, 1, 1, -1, -1 };
private int[] col = { -1, 1, 1, -1, 2, -2, 2, -2 };

private boolean isValid(int x, int y, int N) {
   return (x >= 0 && x < N) && (y >= 0 && y < N);
}

public int findShortestDistance(Cell src, Cell dest, int N)
    {
        // set to check if the matrix cell is visited before or not
        Set<Cell> visited = new HashSet<>();
 
        // create a queue and enqueue the first cell
        Queue<Cell> q = new ArrayDeque<>();
        q.add(src);
 
        // loop till queue is empty
        while (!q.isEmpty())
        {
            // dequeue front cell and process it
            Cell cell= q.poll();
 
            int x = cell.x;
            int y = cell.y;
            int dist = cell.dist;
 
            // if the destination is reached, return distance
            if (x == dest.x && y == dest.y) {
                return dist;
            }
 
            // skip if the location is visited before
            if (!visited.contains(cell))
            {
                // mark the current cell as visited
                visited.add(cell);
 
                // check for all eight possible movements for a knight and enqueue each valid movement
                for (int i = 0; i < row.length; i++)
                {
                    // get the knight's valid position from the current position on the chessboard and enqueue it with +1 distance
                    int x1 = x + row[i];
                    int y1 = y + col[i];
 
                    if (isValid(x1, y1, N)) {
                        q.add(new Cell(x1, y1, dist + 1));
                    }
                }
            }
        }
 
        // return infinity if the path is not possible
        return Integer.MAX_VALUE;
    }

 

The time complexity of the solution is O(N^2) and requires O(N^2) extra space, where N is dimensions of the chessboard.

 

The idea is to use Breadth–first search (BFS) as it is the shortest path problem.