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

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}\).

Quick Answer: 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

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

Loading coding console...