Spins Until Two Different Regions
Updated
Problem statement
A spinner is split into regions. Region i has a positive whole-number weight weights[i]. Let W be the sum of all the weights. Each spin lands in region i with probability weights[i] / W, and the spins are independent.
You keep spinning until the spinner has landed in at least two different regions. Return the expected number of spins. Count every spin, including the first one and the one that lands in the second different region.
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
expectedSpinsForTwoRegions(weights: int[]) → doubleExamples
Example 1
weights = [1,1,2]return = 2.6666666666666665This is the interview case. The regions land with probabilities 1/4, 1/4 and 1/2. If the first spin lands in a region with probability p, every later spin reaches a different region with probability 1 - p, so that takes 1 / (1 - p) more spins on average.
That is 4/3 more spins after a 1/4 region and 2 more after the 1/2 region. The answer is 1 + (1/4)(4/3) + (1/4)(4/3) + (1/2)(2) = 1 + 1/3 + 1/3 + 1 = 8/3, about 2.6667.
Example 2
weights = [1,1]return = 3.0Two regions, each with probability 1/2. After the first spin, each spin reaches the other region with probability 1/2, which takes 2 spins on average. The answer is 1 + 2 = 3.
Example 3
weights = [3,1]return = 4.333333333333333The probabilities are 3/4 and 1/4. If the first spin lands in the 3/4 region, you then wait 4 spins on average for the other region. If it lands in the 1/4 region, you wait 4/3 spins on average. The answer is 1 + (3/4)(4) + (1/4)(4/3) = 1 + 3 + 1/3 = 13/3, about 4.3333.
Constraints
2 <= weights.length <= 10^41 <= weights[i] <= 10^6
More Susquehanna International Group (SIG) Online Assessment questions
- Catch Fish with Reusable BaitsOA · Seen Nov 2026
- Bold Play to Reach a GoalOA · Seen Nov 2026
- Cats, Truth and Who Has MoreOA · Seen Nov 2026
- Counting Cows by Their LegsOA · Seen Nov 2026
- Enough Muffins for the LineOA · Seen Nov 2026
- Expected Consecutive Pairs Among Chosen NumbersOA · Seen Nov 2026
- Four-by-Four Boundary GridOA · Seen Nov 2026
- Frog Paths Without Long RunsOA · Seen Nov 2026
- Higher Roll, or Lose the SumOA · Seen Nov 2026
- Is a Popular Story Fake?OA · Seen Nov 2026
Similar questions at other companies
- Count Valid Square PairsAuxoAI · OA
- Server InvestmentRippling · OARippling interview questions
- Basic Item DiscountsPalantir · OAPalantir interview questions
- Next Pascal Row CoefficientIntuit · OAIntuit interview questions
- Unique Integers That Sum to ZeroNVIDIA · OANVIDIA interview questions
- Count Multiples of Three with Two SevensHudson River Trading · OAHudson River Trading interview questions
- Diagonal Bounce TraversalAutodesk · OAAutodesk interview questions
- Maximum Student-Teacher DistanceChubb · OAChubb interview questions
- Maximum Three-Server Difficulty ScoreVisa · OAVisa interview questions
- Minimum Password IncrementsAccenture · OAAccenture interview questions