Title: Microsoft Interview Problem
Solve it in 10 min!!!
An actual subject: MS Interview problem
This question is asked at Microsoft job interviews. The interviewer said
it should take you 10 min max.
There are 4 men who want to cross a bridge. They all begin on the same
side. You have 17 minutes to get all of them across to the other side. It
is night. There is one flashlight. A maximum of two people can cross at
one time. Any party who crosses, either 1 or 2 people, must have the
flashlight with them. The flashlight must be walked back and forth, it
cannot be thrown etc. Each man walks at a different speed. A pair must
walk together at a rate of the slower man's pace.
Man 1: 1 minute to cross.
Man 2: 2 minutes to cross.
Man 3: 5 minutes to cross.
Man 4: 10 minutes to cross.
For example, if Man 1 and Man 4 walk across first, 10 minutes have elapsed
when they get to the other side of the bridge. If Man 4 returns with the
flashlight, a total of 20 minutes have passed, and you have failed the
mission.
See how quickly you can solve this!
p.s. The flashlight cannot shine a long distance. No one can be carried,
etc. (This is a straightforward problem. There are no tricks.
From: Hank
The numbers represent the men with their respective required crossing
time. SideX represents where the men are after each "move".
Side1 Bridge Side2 Time Elapsed
1,2,5,10
5,10 1,2-> 1,2 2
2,5,10 <-2 1 +2 = 4
2 5,10-> 1,5,10 +10 = 14
1,2 <-1 5,10 +1 = 15
1,2-> 1,2,5,10 +2 = 17