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

- algos August 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you explain the reason for this equation please

- logeshkumarlk1994 August 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

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

- Murali Mohan August 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Murali Mohan August 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- gokayhuz August 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Murali Mohan August 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gokayhuz September 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

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

- PKT October 22, 2013 | Flag
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)

- python November 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

6 moves

- Murali Mohan August 18, 2013 | Flag Reply
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
        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));
    }

}

- codeMonkey August 18, 2013 | Flag Reply
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.

- Anon August 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anon August 19, 2013 | Flag
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;}

- purusharth August 23, 2013 | Flag Reply
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

- PKT October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

May be some DP solution

- krutik February 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Madhur November 06, 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