Problem: this one is a classic that many of you have probably already heard, but all the more reason why it should definitely be included here. four people are on this side of the bridge. the bridge will be destroyed by a bomb in 17 minutes. everyone has to get across before that. problem is that it’s dark and so you can’t cross the bridge without a flashlight, and they only have one flashlight. plus the bridge is only big enough for two people to cross at once. the four people walk at different speeds: one fella is so fast it only takes him 1 minute to cross the bridge, another 2 minutes, a third 5 minutes, the last it takes 10 minutes to cross the bridge. when two people cross the bridge together (sharing the flashlight), they both walk at the slower person’s pace. can they all get across before the bridge blows up?
person A: 1 minute
person B: 2 minutes
person C: 5 minutes
person D:10 minutes
Solution
Of course its possible, otherwise it wouldn’t be a very interesting question. the only trick is in realizing that you want to get the two slowest people across together, because otherwise you are wasting too much time. but then once you get them across, how do you not make one of them walk back with the flashlight? well, you just have one of the fast people already there waiting to sprint the flashlight back across.
1. A & B cross. total time: 2 minutes.
C |==========================| A D | | B |==========================| flashlight 2. B comes back. total time: 4 minutes. C |==========================| A D | | B |==========================| flashlight 3. C & D cross. total time: 14 minutes. B |==========================| A | | C |==========================| D flashlight 4. A comes back. total time: 15 minutes. A |==========================| C B | | D |==========================| flashlight 5. A & B cross. total time: 17 minutes. |========= =============| A | KABOOM! | B |========= =============| C D flashlight
another solution which is valid is to have A bring the flashlight back in step 2. it only changes the solution slightly. this is supposed to be a “classic” microsoft interview question but it seems absurdly easy to be a good interview question (especially coupled with the fact that everyone has probably heard it already).