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 be

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.