Cross the Bridge Puzzle-Asked in Google and Microsoft interviews.

Question:

Four people are on this side of the bridge. Everyone has to get across.

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. What is the minimum time required for all 4 to cross the bridge?

Solution: 17 Minutes

1 minute Person B : 2 minutes
Person C : 5 minutes
Person D : 10 minutes

Let F represents the flashlight.
Person C and D are the slowest guys, if they don’t walk together that it self will make it 15 minutes, In this case (the best way to save time is) :
A,D,F —-Bridge—-> = 10 min
<—-Bridge—-A,F = 1 min (returning with flash light) A,C,F —-Bridge—-> = 5 min
<—-Bridge—-A,F = 1 min A,B,F —-Bridge—-> = 2 min
That makes a total of 19 minutes, but thats not what we want.It means they both should walk together, in this case if they both are walking together, then there should be another person(because if one of them will bring it will take 5 minutes) to bring the flashlight back. So here is the solution…A,B,F —-Bridge—-> = 2 min
<—-Bridge—-A,F = 1 min C,D,F —-Bridge—-> = 10 min
<—-Bridge—-B,F = 2 min A,B,F —-Bridge—-> = 2 min
Total time = 17 minutes.

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Reactions to #defaultbydesign

What’s Your Next Step to Be An Advanced UX Designer?

Let me tell you what UX is really about

Shopee UX study — landing page redesigned for user’s attention

8 websites to download high quality free fonts and make the best use of it

Daily UX Learning journaling

Confronting ‘Onism’

PINK WREATH OBITUARY ANNOUNCEMENT

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

Bee Travel Puzzle

0/1 Knapsack

Leetcode — 1 problem

Spider’s Web Puzzle