Bold Play to Reach a Goal
Updated
Problem statement
You have start chips and want to reach goal chips before you run out. You play rounds. In each round you bet a whole number of chips. You win the round with probability p and then get back your bet plus the same amount again, so your chips go up by the bet. Otherwise you lose the bet. Rounds are independent.
You always play boldly: in each round you bet as many chips as you can, but never more than you need to reach the goal. With c chips, that bet is min(c, goal - c). You stop as soon as you have 0 chips or exactly goal chips. With this rule you never go past the goal.
Return the probability that you reach goal chips. Answers within 10^-9 of the exact value are accepted.
Function
boldPlayWinProbability(start: int, goal: int, p: double) → doubleExamples
Example 1
start = 3goal = 5p = 0.75return = 0.8866396761133604This is the interview case. Let f(c) be the chance of reaching 5 chips from c chips. The bets are:
- From
3, bet2: a win gives5, a loss gives1. Sof(3) = 3/4 + 1/4 * f(1). - From
1, bet1:2or0. Sof(1) = 3/4 * f(2). - From
2, bet2:4or0. Sof(2) = 3/4 * f(4). - From
4, bet1:5or3. Sof(4) = 3/4 + 1/4 * f(3).
The game can come back to 3 chips. Putting the lines together gives f(3) = 3/4 + 27/256 + 9/256 * f(3), so f(3) = 219/247, about 0.8866396761.
Example 2
start = 1goal = 2p = 0.3return = 0.3With 1 chip and a goal of 2, you bet your only chip once. You win with probability 0.3.
Example 3
start = 3goal = 8p = 0.6return = 0.504From 3, bet all 3: a win gives 6, a loss ends the game. From 6, bet 2: a win gives 8, a loss gives 4. From 4, bet all 4: a win gives 8, a loss ends the game.
So the chance is 0.6 * (0.6 + 0.4 * 0.6) = 0.6 * 0.84 = 0.504.
Constraints
2 <= goal <= 10^61 <= start < goal0 <= p <= 1
More Susquehanna International Group (SIG) Online Assessment questions
- Catch Fish with Reusable BaitsOA · 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
- Knights, Knaves and Their StatementsOA · Seen Nov 2026
Similar questions at other companies
- Capping Portfolio WeightsCapstone Investment Advisors · OA
- Repeated Mirror XORMathWorks · OAMathWorks interview questions
- Stacked Item and Category DiscountsPalantir · OAPalantir interview questions
- Find Total CostJP Morgan Chase · OAJP Morgan Chase interview questions
- Macaron Order PriceOpenAI · OAOpenAI interview questions
- Daily Settlement for Long and Short PositionsBelvedere Trading · OA
- Last Object Exit TimeIBM · OAIBM interview questions
- Debug the Risk-Limit QuoterMillennium · OAMillennium interview questions
- Prime Factor VisitationMaven Securities · OAMaven Securities interview questions
- Proportional Momentum Investment StatisticsOptiver · OAOptiver interview questions