Two Envelopes With a Known Range
Updated
Problem statement
A number X is chosen uniformly at random between lo and hi. One envelope gets X dollars and the other gets k × X dollars.
You pick one of the two envelopes, each with chance 1/2, open it and see the amount inside. You know lo, hi and k. Now you may keep your envelope or switch to the other one (you cannot switch back).
Decide when to switch so that the expected amount you take home is as large as possible, and return that expected amount.
Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
bestExpectedAmount(lo: int, hi: int, k: int) → doubleExamples
Example 1
lo = 0hi = 100k = 2return = 93.75This is the interview case. If you see more than 100, your envelope must be 2X, because X is at most 100. Keep it.
If you see an amount y of at most 100, you could hold X = y or 2X = y. The smaller envelope's amounts are spread over 0 to 100 and the bigger one's over 0 to 200, so a given y is twice as likely to come from the smaller one. The chance you hold X is 2/3, and switching gives on average 2/3 × 2y + 1/3 × y/2 = 1.5y, which beats y. So switch.
Now add it up. Half the time you hold X; you always switch and get 2X, which averages 100. The other half you hold 2X; you switch to X when X <= 50 and keep 2X otherwise, which averages 12.5 + 75 = 87.5. The answer is (100 + 87.5) / 2 = 93.75. Never switching would give only 75.
Example 2
lo = 60hi = 100k = 2return = 160.02X is at least 120, so any amount up to 100 is the smaller envelope and any amount of 120 or more is the bigger one. You always know which envelope you hold: switch when you see at most 100, keep otherwise. You end with 2X every time, which averages 2 × 80 = 160.
Example 3
lo = 0hi = 100k = 3return = 144.44444444444446Above 100 you hold 3X, so keep it. At most 100, you hold X with chance 3/4, and switching gives on average 3/4 × 3y + 1/4 × y/3 = 2.25y + y/12, more than y. So switch.
Holding X, you always switch and get 3X, which averages 150. Holding 3X, you switch when X <= 100/3 and keep otherwise, which averages 1250/9, about 138.89. The answer is (150 + 1250/9) / 2 = 1300/9, about 144.444.
Constraints
0 <= lo < hi <= 10^62 <= 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
- Integers With Multiple Sum of Two CubesCharta Health · PHONE SCREEN · ONSITE INTERVIEWCharta Health interview questions
- Dice-Walk Winning ProbabilityGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Logistic Regression with Gradient DescentYahoo · PHONE SCREENYahoo interview questions
- Evaluate an Arithmetic Expression Written in WordsBrex · PHONE SCREEN
- Constant-Time Weighted Pick with an Alias TableEtched · PHONE SCREEN
- Integer to English Words in USD and INR StylesVeeam · PHONE SCREEN
- Adaptive Calibration ErrorOpenAI · PHONE SCREENOpenAI interview questions
- Sum of Smallest Non-DivisorsThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- Square Root FunctionCitadel · PHONE SCREENCitadel interview questions
- Reorderable Task Scheduler With CooldownWaymo · PHONE SCREENWaymo interview questions