Estimate Two Conditional Win Probabilities by Simulation
Company: Thumbtack
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Estimate Two Conditional Win Probabilities by Simulation
You are given a game with three closed doors, labeled `0`, `1`, and `2`. Behind exactly one door is a prize (a "win"); the other two doors hide nothing. The prize is placed uniformly at random — each door is equally likely to hide it.
Each round of the game plays out as follows:
1. The prize is placed uniformly at random behind one of the three doors.
2. The contestant picks one of the three doors uniformly at random.
3. The host, who knows where the prize is, opens **one** of the two remaining doors — a door that the contestant did **not** pick **and** that does **not** hide the prize. If both remaining doors are empty, the host chooses uniformly at random between them.
4. The contestant now follows one of two fixed strategies for the entire experiment:
- **Stay**: keep the originally picked door.
- **Switch**: change to the one remaining unopened door (i.e., not the original pick and not the door the host opened).
The contestant wins the round if their final door hides the prize.
Your task is to write a program that estimates, **by Monte Carlo simulation** (not by an analytic/closed-form probability calculation), the two quantities:
- `p_stay` = P(win | the contestant always stays)
- `p_switch` = P(win | the contestant always switches)
### Input
A single integer `n` on its own line: the number of independent simulated rounds to run for **each** strategy.
- `1 <= n <= 10_000_000`
### Output
Print two space-separated floating-point numbers on one line: `p_stay` and `p_switch`, each the empirical win rate (number of wins divided by `n`) for that strategy, rounded to **2 decimal places**.
For sufficiently large `n`, the estimates should converge to approximately `0.33` and `0.67`.
### Example
```
Input:
1000000
Output:
0.33 0.67
```
### Requirements
- The two probabilities must be obtained from a **simulation** that actually plays the rounds (random prize placement, random initial pick, host opening a valid door), not by printing the known theoretical values directly.
- Use a fixed random seed so the output is reproducible: seed your random number generator with `42` before running the simulation.
- Each strategy is evaluated over its own `n` independent rounds.
- Round each printed probability to exactly 2 decimal places (e.g., `0.33`, `0.67`).
Quick Answer: This question tests practical coding ability in probabilistic simulation, requiring implementation of a Monte Carlo method to estimate conditional win probabilities under two decision strategies. It assesses a data scientist's skill in translating a classic probability scenario into working randomized code rather than relying on closed-form analysis.
You are given a Monty-Hall-style game with three closed doors labeled `0`, `1`, and `2`. Behind exactly one door is a prize (a "win"); the other two hide nothing. The prize is placed uniformly at random.
Each round plays out as follows:
1. The prize is placed uniformly at random behind one of the three doors.
2. The contestant picks one of the three doors uniformly at random.
3. The host, who knows where the prize is, opens **one** of the remaining doors — a door the contestant did **not** pick **and** that does **not** hide the prize. If both remaining doors are empty, the host chooses uniformly at random between them.
4. The contestant follows one of two fixed strategies:
- **Stay**: keep the original pick.
- **Switch**: move to the one remaining unopened door.
Given an integer `n` (the number of independent simulated rounds per strategy), estimate by **Monte Carlo simulation** (not a closed-form formula):
- `p_stay` = empirical P(win | always stay)
- `p_switch` = empirical P(win | always switch)
Return the two probabilities as a list `[p_stay, p_switch]`, each rounded to exactly 2 decimal places. Seed the random number generator with `42` before running the simulation so results are reproducible. For large `n` the estimates converge to approximately `0.33` and `0.67`.
**Constraints:** `1 <= n <= 10_000_000`.
**Note:** the reference implementation uses Python's `random` module seeded with `42`; the exact rounded values for small `n` are CPython-specific, while for large `n` any correct simulation converges to ~0.33 and ~0.67.
Constraints
- 1 <= n <= 10_000_000
- Doors are labeled 0, 1, 2; exactly one hides the prize.
- Prize placement and the contestant's pick are each uniform over the three doors.
- The host opens a door that is neither the contestant's pick nor the prize; if two such doors exist, the host chooses uniformly between them.
- Seed the RNG with 42 before simulating.
- Round each probability to exactly 2 decimal places.
Examples
Input: (10,)
Expected Output: [0.4, 0.6]
Explanation: With only 10 rounds (CPython random seeded with 42), the empirical rates are noisy: stay wins 4/10 = 0.40, switch wins 6/10 = 0.60.
Input: (1000,)
Expected Output: [0.33, 0.66]
Explanation: At 1000 rounds the estimates begin to converge: stay ~0.33, switch ~0.66.
Input: (100000,)
Expected Output: [0.33, 0.67]
Explanation: At 100k rounds the estimates have converged to the theoretical values: stay ~1/3 = 0.33, switch ~2/3 = 0.67.
Input: (1000000,)
Expected Output: [0.33, 0.67]
Explanation: At one million rounds the Monte Carlo estimates are essentially exact: 0.33 for stay and 0.67 for switch.
Hints
- For the STAY strategy you don't even need to model the host: staying wins exactly when your initial pick equals the prize, so p_stay is just the fraction of rounds where pick == prize.
- For the SWITCH strategy, after the host opens a valid door, the switch door is the unique door that is neither your pick nor the host's opened door. Switching wins whenever your initial pick was wrong.
- Seed the RNG with 42 once before each strategy's loop so the run is reproducible, and divide wins by n, rounding to 2 decimals. For large n you should see ~0.33 (stay) and ~0.67 (switch).