How should I practice Two-Player Gambler's Ruin Probability and Simulation?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft onsite interview problems in FastPrep.

Is Two-Player Gambler's Ruin Probability and Simulation associated with Microsoft?

FastPrep tags this as a Microsoft onsite interview coding practice problem when the problem catalog has that company and stage context.

Two-Player Gambler's Ruin Probability and Simulation

Microsoft● HardNEW GRADONSITE INTERVIEW

Learn

Problem statement

Two independent players each start with wealth 1. On each play, a player gains one with probability winProbability and loses one otherwise. A player's game ends upon reaching wealth 0 or target.

Return two values: the exact probability that both players reach zero before target, and the simulated fraction of paired trials in which both reach zero. Each row of trialsA and trialsB contains that player's realized steps as 1 for a win and -1 for a loss, and is guaranteed to end at a boundary.

Function

gamblersRuin(target: int, winProbability: double, trialsA: int[][], trialsB: int[][]) → double[]

Examples

Example 1

target = 3winProbability = 0.5trialsA = [[-1],[1,-1,-1],[1,1]]trialsB = [[-1],[-1],[1,-1,-1]]return = [0.4444444444444444,0.6666666666666666]

For a fair walk from wealth one to boundaries zero and three, one-player ruin probability is 2/3, so both ruin with probability 4/9. Two of the three supplied paired trials have both players ruined.

Example 2

target = 2winProbability = 0.5trialsA = [[-1],[1]]trialsB = [[-1],[-1]]return = [0.25,0.5]

Each player has ruin probability one half; one of two paired simulations ruins both players.

Constraints

2 <= target <= 100
0 < winProbability < 1
1 <= trialsA.length = trialsB.length <= 1000
Every trial row contains only -1 and 1 and reaches zero or target exactly
Results use absolute tolerance 1e-9