Bridge crossing (Microsoft Hiring test)

Posted

A good friend of mine send me this quiz which was found in compendium at her university. The course was about Mathematical Programming. I have copied the quiz directly.

The assignments:

Warning, this assignment is rather hard. It should have been used in a Microsoft during hiring interviews.

Four persons have to cross a bridge. The times each needs to cross it are:

  • 5 min
  • 10 min
  • 20 min
  • 25 min.

It is dark and they only have one lamp, we have the following constraints:

  • the bridge can only be crossed if one has a lamp, while it is too dark.
  • 2 persons at most are allowed to be on the bridge at the same time.
  • the speed of a pair is determined by the speed of the slower person.
  • the lamp can last only an hour.
  • the lamp cannot be thrown.

Can you figure out a way so that the four men can cross the bridge in 60 minutes.

Solution

Here is how I solved it. It is a classical problem where you need to move back and forth a couple of times.

Crossing time for each person

A – 5 minutes.
B – 10 minutes.
C – 20 minutes.
D – 25 minutes.

The plan is as the following

Time Start Movement End
0 minutes A B C D
10 minutes C D A & B walks over A B
15 minutes A C D A walks back B
40 minutes A C & D walks over B C D
50 minutes A B B walks back C D
60 minutes A & B walks over A B C D

Done.

Share on FacebookTweet about this on TwitterShare on LinkedInShare on Google+Share on RedditBuffer this pageEmail this to someone

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Current day month ye@r *