Goldman Sachs Interview Question
InternsCountry: India
Interview Type: In-Person
I think the moves can better be represented by a recurrence relation. There are several bases cases here. If M(n) is the number of moves required on a nxn chessboard, we have the following base cases.
For 3x3 board, M(3) = 4 moves
For 4x4 board, M(4) = 2 moves. LIkewise,
M(5) = 4
M(6) = 4
M(7) = 4
M(8) = 6
M(9) = 6
For n >= 10, We have
M(n) = Min{ Min(i) + Min(j)}, where i+j = n & i>2 & j>2
I don't have a proof of whether or not solving
M(n) = Min{ Min(i) + Min(j)}, where i+j = n & i>2 & j>2
can lead to
4 + ((N-5)/3)*2
But, using the recurrence relation above, a simple DP solution that correctly computes the value is possible.
Erasmus is right for the most part, except there are two important bugs.
The base cases are correct. However, we don't really need that many base cases.
Also there is an off-by-one error. The sum of i and j should be n+1, not n.
And in the function, the Min(a)'s should be M(i)
Here is the complete solution:
M(1) 0
M(2) not defined
M(3) = 4
M(4) = 2
M(5) = 4
M(6) = 4
For n>6;
M(n) = Min{ M(i) + M(j)}, where i+j = n+1 & i>;2 & j>2
This produces:
M(7) = M(4) + M(4) = 4
M(8) = M(5) + M(4) = 6
M(9) = M(6) + M(4) = 6
...
Thanks gokayhuz for informing about the errors. Appreciate it. Could you please give the rationale why i+j should be n+1?
@Erasmus: imagine the knight travelling on the diagonal (1,1 to n,n). The knight will have to travel from 1,1 to k,k (where 1 <= k <= n) first.
In the sum,
- M(n) = Min(M(i) + M(j))
M(i) represents the first part of the move and M(j) represents the second part.
For a 8x8 board, we have the knight move from (1,1) to (8,8). However, the answer we are trying to compute is M(8).
Because we are starting our indices at 1 (and not 0), we need to add 1 to n.
The rationale is easy to visualize or you can reverse-engineer the off-by-one from the numbers as well.
def knight(squares = [( (1, 1), 0 )], seen_pairs = {}):
if not squares: return - 1
x = squares[0][0][0]
y = squares[0][0][1]
step = squares[0][1]
if x == 8 and y == 8:
return step
pairs = [(x - 1, y - 2), (x - 1, y + 2), (x - 2, y + 1), (x - 2, y - 1),
(x + 1, y + 2), (x + 1, y - 2), (x + 2, y + 1), (x + 2, y - 1)]
for new_pair in pairs:
x, y = new_pair
if x >= 1 and x <= 8 and y >=1 and y <= 8 and new_pair not in seen_pairs:
seen_pairs[new_pair] = True
squares.append((new_pair, step + 1))
return knight(squares[1:], seen_pairs)
BFS based algorithm, the equation seems to be right.
public class Knight
{
class Position
{
int x;
int y;
public Position(int x, int y)
{
this.x = x;
this.y = y;
}
/**
* Is the position valide on the chess board.
* @param n size of the chess board
* @return true if valid
*/
public boolean isValid(int n)
{
return isValidIndex(x, n) && isValidIndex(y, n);
}
private boolean isValidIndex(int index, int n)
{
return index >= 0 && index < n;
}
@Override
public int hashCode()
{
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj)
{
if (this == obj)
{
return true;
}
if (obj == null)
{
return false;
}
if (!(obj instanceof Position))
{
return false;
}
Position other = (Position)obj;
if (x != other.x)
{
return false;
}
if (y != other.y)
{
return false;
}
return true;
}
}
/**
* Counts the numbers of moves to move from (0,0) to (n-1, n-1)
* @param n size of the chess board
* @return the number of moves
*/
public int countMoves(int n)
{
return countMoves(n-1, n-1, n);
}
/**
* Counts the numbers of moves to to move from (0,0) to (i, j)
* @param i index horizontally
* @param j index vertically
* @param n size of the chess board
* @return the number of moves
*/
public int countMoves(int i, int j, int n)
{
boolean[][] visited = new boolean[n][n];
// BFS
List<Position> nodesToTry = new LinkedList<Position>();
Map<Position, Position> path = new HashMap<Position, Position>();
nodesToTry.add(new Position(0, 0));
while (!nodesToTry.isEmpty())
{
Position current = nodesToTry.remove(0);
if (current.x == i && current.y == j)
{
// found
break;
}
Position next = new Position(current.x + 2, current.y + 1);
processNext(n, visited, nodesToTry, path, current, next);
next = new Position(current.x + 2, current.y - 1);
processNext(n, visited, nodesToTry, path, current, next);
next = new Position(current.x - 2, current.y + 1);
processNext(n, visited, nodesToTry, path, current, next);
next = new Position(current.x - 2, current.y - 1);
processNext(n, visited, nodesToTry, path, current, next);
next = new Position(current.x + 1, current.y + 2);
processNext(n, visited, nodesToTry, path, current, next);
next = new Position(current.x + 1, current.y - 2);
processNext(n, visited, nodesToTry, path, current, next);
next = new Position(current.x - 1, current.y + 2);
processNext(n, visited, nodesToTry, path, current, next);
next = new Position(current.x - 1, current.y - 2);
processNext(n, visited, nodesToTry, path, current, next);
}
// print path
Position next = new Position(i, j);
Position source = new Position(0, 0);
System.out.printf("%n Path from (%d, %d) to (0, 0) %n", i, j);
int counter = 0;
while (next != null && !next.equals(source))
{
System.out.printf(" (%d, %d) --> ", next.x, next.y);
next = path.get(next);
counter ++;
}
System.out.printf(" (0, 0)");
return counter;
}
public void processNext(int n, boolean[][] visited, List<Position> list, Map<Position, Position> path,
Position current, Position next)
{
if (next.isValid(n) && !visited[next.x][next.y])
{
visited[next.x][next.y] = true;
path.put(next, current);
list.add(next);
}
}
/**
* 5x5 - 4 moves
* 6x6 - 4
* 7x7 - 4
* 8x8 - 6
* 9x9 - 6
* 10x10 - 6
* 11x11 - 8
* 12x12 - 8
*/
@Test
public void testGetPath()
{
assertEquals(2, new Knight().countMoves(4));
assertEquals(4, new Knight().countMoves(5));
assertEquals(4, new Knight().countMoves(6));
assertEquals(4, new Knight().countMoves(7));
assertEquals(6, new Knight().countMoves(8));
assertEquals(6, new Knight().countMoves(9));
assertEquals(6, new Knight().countMoves(10));
assertEquals(8, new Knight().countMoves(11));
assertEquals(8, new Knight().countMoves(12));
assertEquals(10, new Knight().countMoves(16));
assertEquals(4 + ((32-5)/3)*2, new Knight().countMoves(32));
}
}
I think a bi-directional bfs search will be good, as search space is minimum and an overlap is more likely to be detected. Plus optimal solution is guaranteed, as bfs takes cost as number of steps taken.
A BFS might not always lead to the minimal solution.
time complexity O(1)
- algos August 18, 20131x1 - 0 moves
2x2 - 0
3x3 - 4
4x4 - 2
5x5 - 4 moves
6x6 - 4
7x7 - 4
8x8 - 6
9x9 - 6
10x10 - 6
11x11 - 8
12x12 - 8
for board 5x5 to NxN
4 + ((N-5)/3)*2