## Goldman Sachs Interview Question for Interns

Country: India
Interview Type: In-Person

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

time complexity O(1)

1x1 - 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

Comment hidden because of low score. Click to expand.
0

can you explain the reason for this equation please

Comment hidden because of low score. Click to expand.
0

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``````

Comment hidden because of low score. Click to expand.
0

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``

``4 + ((N-5)/3)*2``

But, using the recurrence relation above, a simple DP solution that correctly computes the value is possible.

Comment hidden because of low score. Click to expand.
2

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
...``````

Comment hidden because of low score. Click to expand.
0

Thanks gokayhuz for informing about the errors. Appreciate it. Could you please give the rationale why i+j should be n+1?

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

for N%3 = 0
=> 2*(n)/3

for N%3 = 1
=> 2*(n-1)/3

for N%3 = 2
=> [2*(n-2)/3] + 2

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

``````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)``````

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

6 moves

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

``````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

Map<Position, Position> path = new HashMap<Position, Position>();

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

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

}``````

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

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.

Comment hidden because of low score. Click to expand.
0

I meant a "DFS" might not always lead to an optimal solution.

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

assume a positive integer n and suppose min number of moves =y...
if(N%3=1)
{n = (N-1)/3;
y=2*n;
}
else
{ n= N/3;
y=2*n+2;}

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

for N%3 = 0
=> 2*(n)/3

for N%3 = 1
=> 2*(n-1)/3

for N%3 = 2
=> [2*(n-2)/3] + 2

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

May be some DP solution

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

Except for n = 3, Number of moves = ((n+1)/3)*2

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.

### 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.