Highest Die Roll Wins
Updated
Problem statement
Several players each roll a fair die whose faces show 1 to sides, each face equally likely. The player with the highest roll wins. If several players share the highest roll, only those players roll again, and this repeats until one player is ahead of everyone else.
You are player 0. The array rolls gives each player's first roll: a value from 1 to sides if that player has already rolled, or 0 if that player has not rolled yet.
Return the probability that you win the game. Answers within 1e-6 of the exact value are accepted.
Function
winProbability(sides: int, rolls: int[]) → doubleExamples
Example 1
sides = 6rolls = [0,4,4]return = 0.388888888889Both friends rolled 4. If you roll 5 or 6 (chance 2/6) you win at once. If you roll 4 (chance 1/6) all three players tie and roll again, and each of you then wins with chance 1/3. Anything lower loses. So the answer is 2/6 + 1/6 * 1/3 = 7/18, about 0.388888889.
Example 2
sides = 6rolls = [0,0,0]return = 0.333333333333Nobody has rolled yet and the rules treat all three players the same way, so each player wins with chance 1/3.
Example 3
sides = 6rolls = [4,0,0]return = 0.342592592593You rolled 4. Both friends roll lower with chance (3/6) * (3/6) = 1/4, and then you win. Exactly one friend ties you and the other rolls lower with chance 2 * (1/6) * (3/6) = 1/6, and then you win the two-player re-roll with chance 1/2. Both friends roll 4 with chance 1/36, and then you win with chance 1/3. In total 1/4 + 1/12 + 1/108 = 37/108, about 0.342592593.
Constraints
2 <= sides <= 1002 <= rolls.length <= 500 <= rolls[i] <= 100- Every
rolls[i]is at mostsides.
More Jane Street Phone Screen questions
- Maximum-Scoring Consecutive Tree LevelsPHONE SCREEN · Seen Nov 2026
- Tree Selection and VisibilityPHONE SCREEN · Seen Nov 2026
- Load/Store Arithmetic InterpreterPHONE SCREEN · Seen Oct 2026
- Instrument Stack Language JumpsPHONE SCREEN · Seen Oct 2026
- Run a Stack Language InterpreterPHONE SCREEN · Seen Oct 2026
- Positive-Integer Expression EvaluationPHONE SCREEN · Seen Oct 2026
- Add Two Integers Given as StringsPHONE SCREEN · Seen Sep 2026
- Angle Between Clock HandsPHONE SCREEN · Seen Jul 2026
- Route Length From Two CyclistsPHONE SCREEN · Seen Jul 2026
- Sort TradesPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
Similar questions at other companies
- Dice-Walk Winning ProbabilityGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- 3D Grid Diagonal Walk ProbabilityApple · PHONE SCREENApple interview questions
- Coin Game From The EndsTekion · PHONE SCREENTekion interview questions
- Median of Uniform Draws in an IntervalSusquehanna International Group (SIG) · PHONE SCREENSusquehanna International Group (SIG) interview questions
- Starting Value with the Longest Collatz ChainZipRecruiter · PHONE SCREENZipRecruiter interview questions
- Count Array DerangementsInMobi · PHONE SCREENInMobi interview questions
- Maximum-Product Subarray with an Empty ChoiceAkuna Capital · PHONE SCREENAkuna Capital interview questions
- Probability of Consecutive HeadsSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Count Staircase WaysGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- New 21 Game ProbabilityUiPath · PHONE SCREEN