Compute probability last passenger gets own seat
Company: Schonfeld
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
There are 100 passengers boarding a plane with 100 seats, numbered 1 to 100. Passenger `i` (for 1 ≤ i ≤ 100) has a ticket for seat `i`.
The boarding process is as follows:
1. Passenger 1 is drunk and ignores the seat assignment. They choose **one of the 100 seats uniformly at random** and sit there.
2. For each subsequent passenger `k` from 2 to 100:
- If seat `k` (their assigned seat) is still empty, they sit in seat `k`.
- Otherwise (if their assigned seat is already occupied), they choose **uniformly at random** from all the remaining empty seats and sit in one of those.
You are passenger 100. What is the probability that you end up sitting in your **own assigned seat** (seat 100)?
Give the final probability as a simplified fraction or decimal.
Quick Answer: This question evaluates a candidate's understanding of probability theory, combinatorics, and reasoning about sequential random processes, with emphasis on symmetry and conditional dependence.
There are `n` passengers boarding a plane with `n` seats, numbered `1` to `n`. Passenger `i` holds a ticket for seat `i`.
Boarding proceeds in order:
1. **Passenger 1 is drunk** and ignores the seat assignment, choosing one of the `n` seats **uniformly at random**.
2. For each subsequent passenger `k` (from `2` to `n`):
- If their assigned seat `k` is still empty, they sit in seat `k`.
- Otherwise, they choose **uniformly at random** among all remaining empty seats.
Return the probability that the **last** passenger (passenger `n`) ends up in their **own** assigned seat (seat `n`), as a floating-point number.
This is the classic "lost boarding pass" / Green Book puzzle. Implement it as an exact computation (not a Monte-Carlo estimate) so the answer is deterministic.
**Examples:**
- `n = 1` -> `1.0` (the only passenger must sit in seat 1)
- `n = 2` -> `0.5`
- `n = 100` -> `0.5`
**Hint about the math:** Let `p(m)` be the probability for an `m`-passenger instance. The first disruptor picks uniformly among `m` seats. With probability `1/m` they take seat 1 (last passenger surely succeeds); with probability `1/m` they take seat `m` (last passenger surely fails); otherwise, for a seat `j` with `2 <= j <= m-1`, passenger `j` becomes the new disruptor over `m - j + 1` relevant seats, contributing `p(m - j + 1)`.
Constraints
- 0 <= n <= 100000 (use exact rational arithmetic or the closed form to stay deterministic)
- Return a float; for n >= 2 the exact answer is 0.5
- n = 1 returns 1.0; n <= 0 returns 0.0 by convention
Examples
Input: (1,)
Expected Output: 1.0
Explanation: Only one passenger and one seat; passenger 1 must sit in seat 1.
Input: (2,)
Expected Output: 0.5
Explanation: The drunk passenger sits in seat 1 or seat 2 with equal probability; the last passenger gets their own seat only in the former case.
Input: (3,)
Expected Output: 0.5
Explanation: Enumerating all boarding outcomes gives the last passenger their own seat exactly half the time.
Input: (10,)
Expected Output: 0.5
Explanation: By the symmetry of the recurrence, the probability is 1/2 for any n >= 2.
Input: (100,)
Expected Output: 0.5
Explanation: The original problem: 100 passengers, drunk first passenger; the last passenger gets seat 100 with probability 1/2.
Input: (0,)
Expected Output: 0.0
Explanation: Degenerate empty case: there is no last passenger, so the probability is defined as 0.0.
Hints
- Think recursively about who the current 'disruptor' is. After passenger 1 sits randomly, every later passenger either finds their own seat free or becomes a new disruptor.
- The outcome for the last passenger is decided the moment a disruptor sits in either seat 1 (success) or seat n (failure) — by symmetry these two are equally likely.
- Set up p(1) = 1 and p(m) = 1/m + sum over middle seats of (1/m) * p(m - j + 1), then notice the result collapses to 1/2 for every m >= 2.