Pressing Buttons for Boxes of Money
Updated
Problem statement
There are n closed boxes on a stage. Box i holds amounts[i] dollars and has its own button. Two players, who cannot talk to each other, each press one button at the same time.
- If both press the same button, only that box opens, and they split its money equally.
- If they press different buttons, both of those boxes open, and they split the money of the two boxes equally.
Both players use the same random rule: press button i with probability q_i. There is exactly one such rule that neither player can improve on by changing their own rule alone, and it is also the shared rule that gives each player the most money on average.
Return the expected amount of money each player gets when both use that rule.
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
equilibriumShare(amounts: int[]) → doubleExamples
Example 1
amounts = [60,40]return = 38.0This is the interview game. Say the other player presses $60 with chance q. Pressing $60 yourself pays 30 if they also press $60 and 50 otherwise, so on average 30q + 50(1 - q). Pressing $40 pays 50q + 20(1 - q).
The two are equal at q = 3/5, so both press $60 with chance 3/5. Each player then gets 3/5 × 30 + 2/5 × 50 = 18 + 20 = 38.
Example 2
amounts = [60,40,30]return = 38.333333333333336All three boxes are used. The editorial shows that box i is pressed with chance 1 - c/a_i, where c = 2 / (1/60 + 1/40 + 1/30) = 80/3. That gives chances 5/9, 1/3 and 1/9, which add to 1.
The average amount in the box a player presses is S = 5/9 × 60 + 1/3 × 40 + 1/9 × 30 = 50, and each player gets (c + S)/2 = (80/3 + 50)/2 = 115/3, about 38.33.
Example 3
amounts = [60,40,20]return = 38.0With all three boxes, c = 2 / (1/60 + 1/40 + 1/20) = 240/11 ≈ 21.8, which is more than 20, so the $20 box would need a negative chance. It is never pressed.
The rule is the one from example 1, and each player gets 38. Pressing $20 against it would pay only (20 + 3/5 × 60 + 2/5 × 40)/2 = 36.
Constraints
1 <= amounts.length <= 20001 <= amounts[i] <= 10^6
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
- Piecewise Linear Interpolation and ExtrapolationCitadel · PHONE SCREENCitadel interview questions
- Count Centaur Friend RequestsMeta · PHONE SCREENMeta interview questions
- Linear InterpolatorTwo Sigma · OATwo Sigma interview questions
- Paint the CeilingSnowflake · OASnowflake interview questions
- Apartment Housemate PreferencesGoogle · PHONE SCREENGoogle interview questions
- Top K Pins with Insert and QueryPinterest · PHONE SCREENPinterest interview questions
- Adaptive Calibration ErrorOpenAI · PHONE SCREENOpenAI interview questions
- Aggressive CowsAmazon · PHONE SCREEN
- Find All Pythagorean TripletsDell Technologies · PHONE SCREENDell Technologies interview questions
- Convex Function MinimizationUber · PHONE SCREENUber interview questions