Hi,
Just want to thank you for creating this doc, certainly helped for my interviews! Thought I should give back by suggesting a slightly easier solution for the airplane question (I think yours has a bit too much going on).
Define p_n = probability of last person in their seat if there are n people. Either the first person goes to their seat (with prob 1/n) and everything's fine, or the first person goes to any seat other than the last, in which case we return to the same problem with n-1 people.
So p_n = 1/n + (n-2)/n p_(n-1). Since p_2 = 1/2 it is simple to use induction to prove p_n = 1/2.
Hi,
Just want to thank you for creating this doc, certainly helped for my interviews! Thought I should give back by suggesting a slightly easier solution for the airplane question (I think yours has a bit too much going on).
Define p_n = probability of last person in their seat if there are n people. Either the first person goes to their seat (with prob 1/n) and everything's fine, or the first person goes to any seat other than the last, in which case we return to the same problem with n-1 people.
So p_n = 1/n + (n-2)/n p_(n-1). Since p_2 = 1/2 it is simple to use induction to prove p_n = 1/2.