FastPrepKnight Probability in Chessboard
Problems/Knight Probability in Chessboard

Knight Probability in Chessboard

Goldman Sachs logoGoldman Sachs● MediumFULLTIMEONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: In the second Goldman Sachs round, along with questions about the resume, the report lists Knight Probability in Chessboard, named directly.

The report gives no examples, limits or changes to the usual task. Here you get the standard version: a knight makes k random moves on an n x n board, and you return the chance it never leaves the board. The board size, move count and accepted error are added for this practice version.

The judged task matches the report at about 90%.

An n x n chessboard has its rows and columns numbered from 0 to n - 1. A knight starts on the cell in row row and column column, and it tries to make exactly k moves.

A knight move goes two cells in one direction and then one cell at a right angle, so a knight has 8 possible moves. For each move, the knight picks one of these 8 moves at random, each with the same chance, even if the move takes it off the board. If the knight lands off the board, it stays off and makes no more moves.

Return the probability that the knight is still on the board after it stops moving. Answers within 10^-5 of the correct value are accepted.

Function

knightProbability(n: int, k: int, row: int, column: int) → double

Examples

Example 1

n = 3k = 2row = 0column = 0return = 0.0625

From the corner (0, 0), only 2 of the 8 moves stay on the board: to (1, 2) and to (2, 1). From each of those two cells, again only 2 of the 8 moves stay on the board. So the chance is 2/8 * 2/8 = 1/16 = 0.0625.

Example 2

n = 4k = 1row = 1column = 1return = 0.5

From (1, 1) on a 4 x 4 board, 4 moves stay on the board: to (0, 3), (2, 3), (3, 0) and (3, 2). The other 4 leave it. So the chance is 4/8 = 0.5.

Example 3

n = 1k = 0row = 0column = 0return = 1.0

The knight makes no moves, so it is surely still on the board. The answer is 1.

Constraints

  • 1 <= n <= 25
  • 0 <= k <= 100
  • 0 <= row, column <= n - 1

More Goldman Sachs problems

  • House Robber IIIPHONE SCREEN · Seen Nov 2026
  • Trapping Rain WaterPHONE SCREEN · Seen Nov 2026
  • Maximum Ones After K OperationsOA · Seen Nov 2026
All Goldman Sachs interview questionsSee Goldman Sachs hiring insights
Saved
class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        // Write your code here.
    }
}
Checking account…