Solve drunk-passenger probability and simulate outcome
Overview
This question evaluates probabilistic reasoning and stochastic-process intuition, including use of invariant arguments, closed-form derivations, statistical estimation via Monte Carlo simulation, and analysis of algorithmic time and space complexity.
Upstart
Oct 13, 2025, 9:49 PM
Data Scientist
Technical Screen
Statistics & Math
0
0
Lost Boarding Pass Puzzle: Last Passenger's Seat
Context: Technical screen for a Data Scientist (Statistics & Math).
Setup
- There are n passengers labeled 1..n and n assigned seats labeled 1..n on a single-aisle plane.
- Passenger 1 is drunk and chooses a uniformly random seat among the n seats.
- Each subsequent passenger i (2 ≤ i ≤ n) sits in seat i if available; otherwise they choose uniformly at random from the remaining unoccupied seats.
Tasks
- For n = 100, derive a closed-form expression for the probability that passenger 100 sits in seat 100.
- Generalize and prove your result for arbitrary n ≥ 2, using a brief inductive or invariant-based proof.
- Implement a Monte Carlo simulator (R or Python) that estimates this probability for n = 100 with at least 1e6 trials. Report the estimate, its standard error, and a 95% confidence interval. Verify it agrees with theory within 0.01.
- Discuss the time and space complexity of a naive simulation versus an optimized approach that tracks only the two boundary seats.
Solution
Login required
Show