Airplane Seat Assignment Probability

Airplane Seat Assignment Probability

What is this problem about?

The Airplane Seat Assignment Probability interview question is a famous probability brainteaser. There are $n$ passengers boarding an airplane with $n$ seats. The first passenger lost their ticket and picks a seat at random. Every subsequent passenger takes their assigned seat if it's available; otherwise, they pick an available seat at random. What is the probability that the $n$-th passenger sits in their own assigned seat?

Why is this asked in interviews?

Google and quant-heavy firms ask this to see if a candidate can simplify a complex-looking problem. While it looks like it requires Dynamic Programming or heavy math, the solution reveals a deep insight into symmetry. It tests your ability to think through recursive states.

Algorithmic pattern used

While it can be modeled with Dynamic Programming, the core pattern is Mathematical Induction or Symmetry.

• If $n=1$, the probability is $1$ (100%).
• If $n \geq 2$, the probability is always $0.5$ (50%).

Example explanation

If $n=2$:

• Passenger 1 takes seat 1 (1/2 chance). Passenger 2 gets seat 2. (Win)
• Passenger 1 takes seat 2 (1/2 chance). Passenger 2 must take seat 1. (Loss) Result: 0.5.

For larger $n$, the logic holds because the process only ends when someone finally picks either seat 1 (allowing everyone else to sit correctly) or seat $n$ (preventing the last person from sitting correctly). Since seat 1 and seat $n$ are treated identically by anyone "displaced" from their seat, the chances of picking one over the other are equal.

Common mistakes candidates make

• Complex DP: Writing a massive recursive function with memoization. While correct, it's unnecessary and might lead to time-limit errors if not optimized.
• Overthinking: Trying to calculate the probability for every single passenger's seat instead of focusing solely on the $n$-th passenger.

Interview preparation tip

If a probability question seems incredibly complex but the answer for $n=2$ and $n=3$ is the same, try to look for a symmetry argument. Many "random choice" problems in interviews boil down to a simple 50/50 or $1/n$ result.