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 [email protected]. 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.
If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:
the answer is 5minutes, because the person who takes 1 minute will carry the other person and leave him to the other side,then will come back in an another minute,will carry the other person come back,will take the last person,so he walked over the bridge 5 times that is 5 minutes taken.
i think 17min. is ideal answer
How is it possible for people with different speeds to go together ? Won’t the slower one fall short of light? And why is the time mentioned to cross the bridge considered the miinimum time? If considered the total time required then the answer is 13 mins!!
A+C go together= 1 min
R goes back (takes 2 mins now) = 2 mins
R left on the other side, now Q+S 2 mins each = 2 mins
S takes 4 mins to back= 4 mins
S+R cross the bridge 4 mins each= 4 mins
Total= 13 minutes
10 minutes. Give the torch to the 10 minute guy and have him start moving. Then 1 walks across. Then 2 walks across. Then 7 walks across. 10 finally reaches the other side with the torch at the same time as 7, and the torch was on the bridge the whole time. Done.
1 & 2 go together time taken 2 min
1 comes back to give the torch 1 min
7 &10 comes together time taken 10 min
2 goes alone to bring 1 time taken 2 min
2 &1 return together time taken 2 min
total time=2+1+10+2+2=17 min
21 mins
Please clarify me on with out torch how B and C will start 2 and 7 minutes
A -> 1 min
B -> 2 min
C -> 7 min
D -> 10 min
1) A & B both will start, when A reached other side B will be exactly at middle.
So, time taken is 1 min.
2) From there B will come back. time taken to return is 1 min.
3) Now both C & D will start, both will cross the bridge. Time taken is 10 min.
4) A will come back. Time taken is 1 min.
5) A & B both will cross, time taken is 2 min.
Total time = 1 + 1 + 10 + 1 + 2 = 15 mins
@pokey909: Ah, but you didn’t understand the genius of Chris p’s answer.
The question technically only required everyone to cross, not to stay on the other side. 🙂
i burned the bridge for light and then crossed 1 following 2 following 7 following 10. 12 or 13 mins. This might save one minute of crossing time. a little unsure about that. 12 or 13 mins.
Use torch to light bridge on fire for light. 10 follows 7. 2 follows 1. 12 mins total crossing time. yay!!! prolly have to swim back.
@arun
how can you assume that A can go without the torch… ? this is out of the box answer no doubt but.. i still think better one is 17 min
now i understand what the interviewer meant when he said, “Think out of the box,….”
Yeah Arun and Michael Wales are right I guess,….maybe that’s what the interviewer expected when he asked me this question instead of the usual 17 answer
answer is right one….
shortest time possible is only 17 minutes …
because 1 and 2 are fast ones to cross the bridge they are sent back and thru….
@Chris p: But now 1 is still on the other side without a torch. So no, thats not a solution.
1 and 2 cross, 1 comes back. 3 mins total
7 and 10 cross. 10 mins total
13 mins total
All have crossed which is all the question required.
Answer is 17.
@Sanjeev,
bridge is too dangerous to cross without ‘one’.
The ‘one’ means tourch.
bridge is too dangerous to cross without one.
so whole travel two will with each other
17 is the ideal answer
Fantastic content:) I will require some time to entertain the article:)
How can D hold the torch as If A crosses after 1 minute How will B start without torch because at that point of time D must have reached some point..
5 minutes – the person who takes 1 minute just carries the others 😉
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.
@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.
@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. 😀
A and D cross the bridge. That is 10 mins right there… Can you explain it a little more?
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…