How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Google during technical interviews.

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.

Input: (2, 2, 3)

Expected Output: 0.4444444444444444

Explanation: You win only by stopping exactly at 2. This happens with rolls [2] or [1,1], so the probability is 1/3 + 1/9 = 4/9.

Input: (0, 0, 6)

Expected Output: 1.0

Explanation: You start at position 0, and since 0 >= mn, the game is already over. Position 0 is inside [0, 0], so you win with probability 1.

Input: (6, 10, 5)

Expected Output: 1.0

Explanation: Just before the last roll, your position is at most 5. After adding a value from 1 to 5, the final position must lie in [6, 10], which is entirely inside the winning range.

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.

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.