How should I practice Probability of Reaching a Target Interval by Dice Rolls?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen problems in FastPrep.

Is Probability of Reaching a Target Interval by Dice Rolls associated with Google?

FastPrep tags this as a Google phone screen coding practice problem when the problem catalog has that company and stage context.

Probability of Reaching a Target Interval by Dice Rolls

Google● HardNEW GRADPHONE SCREEN

Learn

Problem statement

You start at position 0 on an infinite one-dimensional grid. On every turn, independently choose a uniformly random integer from 1 through k and move that many positions to the right.

You win as soon as you land at any position in the inclusive interval [minTarget, maxTarget]. You lose if you move past maxTarget before landing in the interval.

Return the probability of winning. Answers within 1e-9 of the exact probability are accepted.

Function

reachIntervalProbability(k: int, minTarget: int, maxTarget: int) → double

Examples

Example 1

k = 2minTarget = 2maxTarget = 2return = 0.75

Rolling 2 wins immediately. After rolling 1, the next roll must be 1. The probability is 1/2 + (1/2)(1/2) = 3/4.

Example 2

k = 6minTarget = 1maxTarget = 1return = 0.16666666666666666

Only a first roll of 1 lands on the one-position target; every larger roll immediately passes it.

Example 3

k = 3minTarget = 2maxTarget = 3return = 0.8888888888888889

A first roll of 2 or 3 wins. After a first roll of 1, rolling 1 or 2 wins and rolling 3 loses.

Constraints

1 <= k <= 200000.
1 <= minTarget <= maxTarget <= 200000.
Every roll is independent and every value from 1 through k is equally likely.