Same Face Many Times in a Row
Updated
Problem statement
You roll a fair die with d faces, numbered 1 to d, again and again. One face, say face d, is the target.
Return the expected number of rolls until the target face has come up k times in a row, counting every roll including the last one.
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
expectedRollsForRun(d: int, k: int) → doubleExamples
Example 1
d = 6k = 1return = 6.0This is the first interview question. Each roll is a 6 with chance 1/6, so the wait for the first 6 is 6 rolls on average.
Example 2
d = 6k = 2return = 42.0This is the second interview question, two 6s in a row. First get one 6, which takes 6 rolls on average. Then roll once more: with chance 1/6 it is a 6 and you are done; otherwise you start over. So T = (6 + 1) + (5/6) T, which gives T = 6 × 7 = 42.
Example 3
d = 2k = 3return = 14.0A coin with heads as the target, three heads in a row. Two in a row takes 2 × (2 + 1) = 6 tosses on average, and three takes 2 × (6 + 1) = 14.
Constraints
2 <= d <= 1001 <= k <= 100
More Susquehanna International Group (SIG) Phone Screen questions
- Dice Sum That Is a Multiple of mPHONE SCREEN · Seen Nov 2026
- Find Median from Data StreamPHONE SCREEN · Seen Nov 2026
- Painting Arcs to Nearest Neighbors on a CirclePHONE SCREEN · Seen Sep 2026
- Filter Movies by Inclusive Year RangePHONE SCREEN · Seen Jul 2026
- Best Single Reroll for Five DicePHONE SCREEN · Seen Feb 2026
- Catching the Bus to the MoviePHONE SCREEN · Seen Jan 2026
- Two Dice Summing to a TargetPHONE SCREEN · Seen Jan 2026
- Median of Uniform Draws in an IntervalPHONE SCREEN · Seen Oct 2025
- One Number Is the Average of the Other TwoPHONE SCREEN · Seen Jun 2025
- Which Coin Pattern Shows Up FirstPHONE SCREEN · Seen May 2025
Similar questions at other companies
- Automation Pipeline, Part 1: Single WorkerPlaid · PHONE SCREENPlaid interview questions
- Subtract Two Large Number StringsStackAdapt · PHONE SCREENStackAdapt interview questions
- Circular Primes Below a LimitAmazon · PHONE SCREEN
- Palindrome NumberKotak Mahindra Bank · PHONE SCREENKotak Mahindra Bank interview questions
- Streaming AverageXantium · PHONE SCREEN
- Fair Coin from a Biased CoinAnthropic · PHONE SCREENAnthropic interview questions
- Stack Formula InterpreterTypeSafe AI · PHONE SCREEN
- Employee Count Median, Mean and ModeClay · PHONE SCREEN
- Newton Square Root to a Guaranteed ToleranceSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Biased Coin: Probability of Exactly h HeadsAkuna Capital · PHONE SCREENAkuna Capital interview questions