9 ms·

> 100 passengers have queued up to board a plane, and are lined up in the order of the seats on the plane (n=1..100). However, the first person lost his ticket

> 100 passengers have queued up to board a plane, and are lined up in the order of the seats on the plane (n=1..100). However, the first person lost his ticket and selects a random seat. The remaining passengers will occupy their assigned seat if it is available, or a random seat otherwise. What is the probability that passenger 100 sits in seat 100? It really worried me that I couldn't figure out how to work that out. I thought about what I'd do in an interview if I was asked that, and I figured (if I had my laptop) I'd write some code. So I gave myself 5 minutes by the clock, and wrote a little python program that simulated the situation and counted the results. I ran 5 million iterations, which with pypy took 59 seconds. The number I got out was a 97.335% chance of person 100 being in seat 100. I have 3 questions: 1. Is that the right answer? 2. How are you supposed to work it out? 3. Would working it out the proper way take less than 6 minutes? Edit: It seemed like too high a number, which is part of why I asked. I looked through my code and found a dumb error - I forgot to remove the seat from the 'available' list if the person finds their assigned seat. That's what happens when you write code on a 5 minute deadline. Now I'm consistently getting 49.9%, which seems more reasonable.

bearmf 15y ago
1. Wrong 2. Start with 2 passengers instead of 100 3. Rigorous proof would take a bit longer, say 15 minutes
dkokelley 15y ago
I have no idea if that is correct, but my initial intuition was that it would be a high percentage like you found. However, now that I'm thinking about it, I believe the answer is closer to 50%. When passenger 100 begins to board, there are only two possible configurations he can find the seats in: seat 1 available or seat 100 available. If Passenger 1 sits in seat 100, then passengers 2-99 will sit in their correct seats, leaving only seat 1. If passenger 1 sits in seat 1, passengers 2-99 will sit correctly and leave only seat 100 for passenger 100. If passenger 1 sits anywhere else (say, seat 50), passengers 2 - 49 will fill correctly, passenger 50 will have to sit in seat 1 or 51-100. The moment a passenger randomly selects seat 1 or 100, the remaining passengers will sit correctly (except for passenger 100). It is impossible for any seats other than 1 or 100 to be left for passenger 100 to select. From looking at it, I don't believe there is any bias for the end configuration to leave seat 100 open more than seat 1, and I believe that in an interview situation, you would be expected to intuit this by "talking it out". If I'm right (and I could still be very wrong), this is more of a probabilistic brainteaser than a programming interview question.
- bannerts 15y ago
  This seems to make a lot of sense to me. It appears that in every situation starts off with a passenger randomly selecting a seat, summarized as either sitting in (a) seat 100 [Fail], (b) seat 1 [Success] or (c) some other seat [?]. Options (a) and (b) always have equal likelihoods while option (c) simply forces a later passenger to go through the same random process.
- deleted 15y ago
  [deleted]
dxbydt 15y ago
Its 50%. For 3 passengers the seating possibilities are {123,213,231,321}, so 3 gets to sit on seat 3 50% of the time. For 4 passengers the seating possibilities are {1234,2134,2314,2341,2431,3241,3214,4231}, so 4 gets to sit on seat 4 50% of the time. From there you can do a proof by induction. If you like code: ---- import util.{Random=>rng} import collection.mutable.ArrayBuffer object passengers { def main(args:Array[String]) = { val n = args(0).toInt val simulations = args(1).toInt val happyLast = (1 to simulations).map(_=> { val seats = ArrayBuffer.fill[Int](n+1)(0) val taken = new ArrayBuffer[Int] val all = (1 to n).toSeq val seat = rng.shuffle(all).head seats(seat) = 1 taken += seat (2 to n).foreach( p=> { val seat = seats(p) match { case 0=> p case x=> rng.shuffle(all.diff(taken)).head } seats(seat) = p taken += seat }) seats(n) == n }) println( happyLast.filter(x=>x).size*1.0d/simulations ) } } ----- >scala -cp classes passengers 100 100000 >0.4997
- lgieron 15y ago
  Minor comment from a Scala fan - on that last line you could have used: happyLast.count(_ == true) instead of: happyLast.filter(x=>x).size
- graphene 15y ago
  shouldn't that be {123, 213, 312, 321}? ie 231 is not possible since after 1 randomly decides to sit at 3, 2 has no reason to go sit in seat 1. This doesn't change the answer to the problem though I think.
  - dxbydt 15y ago
    uh, nope. xyz => 1 sits on seat x, 2 on seat y, 3 on seat z So the only possibilities are: 123: 1 sits on seat 1, 2 on seat 2, 3 on seat 3 213: 1 sits on seat 2, 2 on seat 1, 3 on seat 3 231: 1 sits on seat 2, 2 on seat 3, 3 on seat 1 321: 1 sits on seat 3, 2 on seat 2, 3 on seat 1 passenger 3 is happy twice out of 4, hence 50% In the code, the happyLast variable counts the number of times the last passenger is happy ( happy == when he gets his assigned seat)
VMG 15y ago
I think this is more slightly more on-topic as a reply here > Consider the integers from [0,1000]. Suppose a particle starts at position n. At discrete instants of time t=0,1,2,…, the particle moves up or down with p=0.5. What is the probability that the particle reaches 0 before t=1000? The answer is 50%, right? I can't explain it properly, but my thinking is that the random walk is symmetric and 0 and 1000 should have equal weights. Maybe a good explanation is harder than the correct answer in this case.
- yummyfajitas 15y ago
  The particle doesn't necessarily start out in the middle.
  - VMG 15y ago
    So the question is "How likely is for a particle to reach 0 or 1000 depending on the starting position"? Then I got the question wrong, thinking it was about the average likelihood for many particles.
- mturmon 15y ago
  The problem may have a simple answer, but 0.5 is not it, because the answer will be a function of n, the starting position. If n is near 0, the chance you hit zero before 1000 steps is larger. The keyword is "random walk hitting time".
- dxbydt 15y ago
  I believe the right answer is about 2.5% (0.0247) Here's some imperative scala: object particle { def main(args:Array[String]) = { val simulations = args(0).toInt val rng = new util.Random val reachedZero = (1 to simulations).map(_=> { var t = 0 var z = 1+rng.nextInt(1000) do { z += {if (rng.nextBoolean) 1 else -1} t +=1 } while( z != 0 && t<1000) z==0 }) println( reachedZero.count(_==true)*1.0d/simulations ) } } --- >scala particle 1000000 >0.024782 Some intuition: If there were only 2 positions {1,2}, and you picked 1 with probability 0.5, you could get to 0 by going down once with probability 0.5. Going up wouldn't help since you'd have to go down to be back at 1, at which point you've exhausted your chances. Suppose you picked 2 with probability 0.5, you'd have to go down twice consecutively to hit 0, which has a probability of 0.5^2. So overall, your probability is 0.5^2 + 0.5^3 = 0.375 You can try working it out with 3 positions & 3 turns, and suddenly its not so easy....:)

bearmf 15y ago

1. Wrong 2. Start with 2 passengers instead of 100 3. Rigorous proof would take a bit longer, say 15 minutes

dkokelley 15y ago

I have no idea if that is correct, but my initial intuition was that it would be a high percentage like you found. However, now that I'm thinking about it, I believe the answer is closer to 50%. When passenger 100 begins to board, there are only two possible configurations he can find the seats in: seat 1 available or seat 100 available. If Passenger 1 sits in seat 100, then passengers 2-99 will sit in their correct seats, leaving only seat 1. If passenger 1 sits in seat 1, passengers 2-99 will sit correctly and leave only seat 100 for passenger 100. If passenger 1 sits anywhere else (say, seat 50), passengers 2 - 49 will fill correctly, passenger 50 will have to sit in seat 1 or 51-100. The moment a passenger randomly selects seat 1 or 100, the remaining passengers will sit correctly (except for passenger 100). It is impossible for any seats other than 1 or 100 to be left for passenger 100 to select. From looking at it, I don't believe there is any bias for the end configuration to leave seat 100 open more than seat 1, and I believe that in an interview situation, you would be expected to intuit this by "talking it out". If I'm right (and I could still be very wrong), this is more of a probabilistic brainteaser than a programming interview question.

bannerts 15y ago
This seems to make a lot of sense to me. It appears that in every situation starts off with a passenger randomly selecting a seat, summarized as either sitting in (a) seat 100 [Fail], (b) seat 1 [Success] or (c) some other seat [?]. Options (a) and (b) always have equal likelihoods while option (c) simply forces a later passenger to go through the same random process.
deleted 15y ago
[deleted]

dxbydt 15y ago

Its 50%. For 3 passengers the seating possibilities are {123,213,231,321}, so 3 gets to sit on seat 3 50% of the time. For 4 passengers the seating possibilities are {1234,2134,2314,2341,2431,3241,3214,4231}, so 4 gets to sit on seat 4 50% of the time. From there you can do a proof by induction. If you like code: ---- import util.{Random=>rng} import collection.mutable.ArrayBuffer object passengers { def main(args:Array[String]) = { val n = args(0).toInt val simulations = args(1).toInt val happyLast = (1 to simulations).map(_=> { val seats = ArrayBuffer.fill[Int](n+1)(0) val taken = new ArrayBuffer[Int] val all = (1 to n).toSeq val seat = rng.shuffle(all).head seats(seat) = 1 taken += seat (2 to n).foreach( p=> { val seat = seats(p) match { case 0=> p case x=> rng.shuffle(all.diff(taken)).head } seats(seat) = p taken += seat }) seats(n) == n }) println( happyLast.filter(x=>x).size*1.0d/simulations ) } } ----- >scala -cp classes passengers 100 100000 >0.4997

lgieron 15y ago
Minor comment from a Scala fan - on that last line you could have used: happyLast.count(_ == true) instead of: happyLast.filter(x=>x).size
graphene 15y ago
shouldn't that be {123, 213, 312, 321}? ie 231 is not possible since after 1 randomly decides to sit at 3, 2 has no reason to go sit in seat 1. This doesn't change the answer to the problem though I think.
- dxbydt 15y ago
  uh, nope. xyz => 1 sits on seat x, 2 on seat y, 3 on seat z So the only possibilities are: 123: 1 sits on seat 1, 2 on seat 2, 3 on seat 3 213: 1 sits on seat 2, 2 on seat 1, 3 on seat 3 231: 1 sits on seat 2, 2 on seat 3, 3 on seat 1 321: 1 sits on seat 3, 2 on seat 2, 3 on seat 1 passenger 3 is happy twice out of 4, hence 50% In the code, the happyLast variable counts the number of times the last passenger is happy ( happy == when he gets his assigned seat)

VMG 15y ago

I think this is more slightly more on-topic as a reply here > Consider the integers from [0,1000]. Suppose a particle starts at position n. At discrete instants of time t=0,1,2,…, the particle moves up or down with p=0.5. What is the probability that the particle reaches 0 before t=1000? The answer is 50%, right? I can't explain it properly, but my thinking is that the random walk is symmetric and 0 and 1000 should have equal weights. Maybe a good explanation is harder than the correct answer in this case.

yummyfajitas 15y ago
The particle doesn't necessarily start out in the middle.
- VMG 15y ago
  So the question is "How likely is for a particle to reach 0 or 1000 depending on the starting position"? Then I got the question wrong, thinking it was about the average likelihood for many particles.
mturmon 15y ago
The problem may have a simple answer, but 0.5 is not it, because the answer will be a function of n, the starting position. If n is near 0, the chance you hit zero before 1000 steps is larger. The keyword is "random walk hitting time".
dxbydt 15y ago
I believe the right answer is about 2.5% (0.0247) Here's some imperative scala: object particle { def main(args:Array[String]) = { val simulations = args(0).toInt val rng = new util.Random val reachedZero = (1 to simulations).map(_=> { var t = 0 var z = 1+rng.nextInt(1000) do { z += {if (rng.nextBoolean) 1 else -1} t +=1 } while( z != 0 && t<1000) z==0 }) println( reachedZero.count(_==true)*1.0d/simulations ) } } --- >scala particle 1000000 >0.024782 Some intuition: If there were only 2 positions {1,2}, and you picked 1 with probability 0.5, you could get to 0 by going down once with probability 0.5. Going up wouldn't help since you'd have to go down to be back at 1, at which point you've exhausted your chances. Suppose you picked 2 with probability 0.5, you'd have to go down twice consecutively to hit 0, which has a probability of 0.5^2. So overall, your probability is 0.5^2 + 0.5^3 = 0.375 You can try working it out with 3 positions & 3 turns, and suddenly its not so easy....:)