Compute winning probability on 1D dice walk
Company: Google
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are on an infinite 1D number line starting at position 0. Repeatedly roll a fair die that returns an integer uniformly at random from 1 to K (inclusive), and move forward by that many steps.
You **win** if you ever land on a position within the target interval \([mn, mx]\) (inclusive). You **lose** if you jump past the interval, i.e., your position becomes \(> mx\) without ever landing in \([mn, mx]\).
Given integers \(K\), \(mn\), and \(mx\) (with \(1 \le mn \le mx\)), compute the probability of winning starting from position 0.
Return the probability as a floating-point value (or as an exact fraction if you prefer), with acceptable error \(\le 1e{-6}\).
Overview: This question evaluates understanding of probability theory and discrete stochastic processes, specifically reasoning about random walks and event probabilities over (potentially infinite) state spaces.
You are standing at position 0 on an infinite 1D grid. On each turn, you roll a fair k-sided die whose outcomes are the integers 1 through k, each with equal probability, and move to the right by that many cells.
The game ends immediately when your position becomes at least mn.
- If your final position is in the inclusive interval [mn, mx], you win.
- If your final position is greater than mx, you lose.
Return the probability of winning.
Your solution should compute the probability analytically, not by simulation.
Constraints
- 0 <= mn <= mx <= 100000
- 1 <= k <= 100000
- Each die outcome from 1 to k is equally likely
Examples
Input: (3, 3, 2)
Expected Output: 0.625
Explanation: You win only if the stopping position is exactly 3. Winning roll sequences are [1,1,1], [1,2], and [2,1], with total probability 1/8 + 1/4 + 1/4 = 5/8 = 0.625.
Input: (1, 2, 3)
Expected Output: 0.6666666666666666
Explanation: The game stops after the first roll because mn = 1. You win if the die shows 1 or 2, so the probability is 2/3.
Hints
- Let dp[s] represent the probability of reaching total s while the game is still allowed to continue. Each state receives probability from the previous k states.
- A naive DP would sum k values for every position. Use a sliding window to maintain the sum of the last k active probabilities in O(1) per state.
Community answers
Answer by Luna
def win_probability(mn: int, mx: int, k: int) -> float:
"""
Return the probability of winning the dice game.
Start at position 0.
On each turn, move right by a uniformly random integer in [1, k].
The game stops immediately once position >= mn.
Win if the final position is in [mn, mx].
Lose if the final position is > mx.
"""
if k <= 0:
raise ValueError("k must be positive")
# The game is already over before taking any move.
if mn <= 0:
return 1.0 if 0 <= mx else 0.0
# There is no possible winning terminal position.
if mx < mn:
return 0.0
# dp[pos] = probability of eventually winning when currently at pos.
#
# We only need positions up to mn + k - 1:
# before the final roll, the largest possible position is mn - 1;
# after rolling at most k, the largest terminal position is mn + k - 1.
dp = [0.0] * (mn + k)
# Terminal states:
#
# Once pos >= mn, the game ends immediately.
# Positions in [mn, mx] are wins; positions > mx are losses.
#
# We only fill terminal positions through mn + k - 1 because no larger
# position can be reached on the first roll that ends the game.
for pos in range(mn, mn + k):
if pos <= mx:
dp[pos] = 1.0
# Otherwise dp[pos] remains 0.0: terminal loss.
# For pos < mn:
#
# dp[pos] = (dp[pos + 1] + dp[pos + 2] + ... + dp[pos + k]) / k
#
# Start with pos = mn - 1, whose next positions are:
# mn, mn + 1, ..., mn + k - 1.
window_sum = sum(dp[mn:mn + k])
# Compute dp values backward: mn - 1, mn - 2, ..., 0.
for pos in range(mn - 1, -1, -1):
# Each die outcome 1 thro