Question: Four people need to cross a rickety bridge at night. Unfortunately, they have only one torch and the bridge is too dangerous to cross without one. The bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person: 1 min, 2 mins, 7 mins and 10 mins. What is the shortest time needed for all four of them to cross the bridge?
Answer: The initial solution most people will think of is to use the fastest person as an usher to guide everyone across. How long would that take? 10 + 1 + 7 + 1 + 2 = 21 mins. Is that it? No. That would make this question too simple even as a warm up question.
Let’s brainstorm a little further. To reduce the amount of time, we should find a way for 10 and 7 to go together. If they cross together, then we need one of them to come back to get the others. That would not be ideal. How do we get around that? Maybe we can have 1 waiting on the other side to bring the torch back. Ahaa, we are getting closer. The fastest way to get 1 across and be back is to use 2 to usher 1 across. So let’s put all this together.
1 and 2 go cross
2 comes back
7 and 10 go across
1 comes back
1 and 2 go across (done)
Total time = 2 + 2 + 10 + 1 + 2 = 17 mins
If you have any questions, please feel free to send me an email at support@mytechinterviews.com. If you have any interview questions which you feel would benefit others, I would love to hear about it.
If you like this post, please Digg it or give it a thumbs up on StumbleUpon.
Related posts:
I think it takes only 10 minutes
Lets identify each of them as A (1 min), B (2 min), C (7 min) and D (10 min)
Step 1: A and D start together.
Step 2 : After 1 minute, A has crossed the bridge. Now B starts
Step 3: After another 2 minutes (total 3 minutes), B has crossed. Now C starts
Step 4: C and D cross the bridge together at the 10th minute…
D can hold the torch…
A and D cross the bridge. That is 10 mins right there… Can you explain it a little more?
@Aswin
Arun is basically saying, D crosses so slowly that his use of the torch should be sufficient A-C to get across the bridge.
So, A and D start, with D holding the torch, and when A is across (1 minute total), B goes (3 min total), and then C goes (10 minute total). At this time, D will have crossed as well – bring the entire time down to 10 minutes.
It’s definitely an outside the box answer.
@Arun; it depends on if the torch light is enought to illuminate the whole bridge, and if it were, your answer would be sound. Consider minute 9.00: D is 9/10th across, but A is just starting (0/10th across).
If it were bright enough to be suitable, there is no need to even carry it, it could have been left at one end. The expectation is that the 2 travellers must stay together, as their light is shared.
I would suggest that your answer fails here: “only one torch and the bridge is too dangerous to cross without one”. Your answer has 3 of the 4 without a torch for their whole traversal, aside from when overtaking D.
Another point is that *either* 1 or 2 can make the first journey back, with the other coming back next. In effect we are swapping step 2 and 4 of the stated answer.