How should I practice Knight Exit Probability?

Start by reading the full statement, solve the visible examples, then compare the pattern against related InMobi onsite interview problems in FastPrep.

Is Knight Exit Probability associated with InMobi?

FastPrep tags this as a InMobi onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Dynamic Programming

Knight Exit Probability

Learn this problem

● Medium

InMobiFULLTIMEONSITE INTERVIEW

Problem statement

A knight starts at position (row, column) on an n x n chessboard. Rows and columns are zero-indexed.

The knight attempts exactly k moves. On every move it chooses each of its eight standard knight moves with equal probability. If a chosen move lands outside the board, the knight leaves the board and remains outside for all remaining moves.

Return the probability that the knight has left the board after the k attempted moves. Answers within 10^-6 of the exact value are accepted.

Function

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

Examples

Example 1

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

Only two of the eight first moves stay on the board. From either surviving square, two of the next eight moves stay on the board, so the survival probability is 4 / 64 and the exit probability is 60 / 64 = 0.9375.

Example 2

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

Every knight move from the only square leaves the board.

Constraints

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