Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem
3.
Solution
4.
Frequently Asked Questions
4.1.
Why don’t we send everyone across the bridge in one go as it will take 10 minutes only?
4.2.
When the 10-minute person and 1-minute person cross the bridge, why do we take the final time as 10 minutes?
4.3.
Do I need to memorize all the puzzles?
4.4.
Why are puzzles important?
4.5.
Are puzzles asked in the interview of IT companies?
5.
Conclusion
Last Updated: Mar 27, 2024

Cross the Bridge

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Interview Puzzles

Introduction

Cross the bridge is a very famous puzzle. It has been asked in companies like Google and Microsoft. We have discussed the puzzle in this article. After reading the problem statement, try solving the puzzle, then only move to the solution part. This way, you will understand the concept behind this puzzle. So let’s begin.

Problem

There are four people on one side of the bridge. All of them need to cross the bridge. Since its night time, they need to carry a torch to cross the bridge. The problem is that there is only one torch available, and at most, two people can cross the bridge at a time. The time taken by each of them is given below.

  • Person A takes 1 minute
  • Person B takes 2 minutes
  • Person C takes 5 minutes
  • Person D takes 10 minutes

When two people cross the bridge together, they walk at a slower person’s pace. For example: If A and D are crossing the bridge together, then it will take them 10 minutes to cross the bridge.

Find the minimum time in which each of them can cross the bridge.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution

Let’s begin by noting the critical points in this puzzle.

  • Torch needed to cross the bridge, and there was only one torch.
  • Almost two people can cross the bridge at a time.
  • If two people are crossing, then they walk at a slower person’s pace.

We can conclude that each time two people cross the bridge taking the torch, one of them returns to bring the torch back.

The first solution that comes to mind is that A is the fastest, so he should be the one to take the torch back each time. Let’s see how much time this takes.

illustration image

We will address the person taking ‘t’ time to cross the bridge as person t.

  • Initially, we have put the time as zero.
  • Person-1 and person-10 cross the bridge together, taking the torch with them. Time is 10 minutes as they move at a slower person’s pace.
  • Person-1 returns with the torch. It takes 1 minute time.
  • Person-1 and person-5 cross the bridge together with the torch. It takes 5 minutes.
  • Person-1 returns with the torch. It takes 1 minute time.
  • Person-1 and person-2 cross the bridge together with the torch. It takes 2 minutes to cross them.

The total time taken to cross the bridge, in this case, is 19 minutes. Can we do better than this?

Yes, we can. We can observe that it takes 10 + 5 minutes for the two slowest persons if we transport them separately. But if we transport them together, it will take only 10 minutes. So we can try doing this in some way.

We can cross the bridge optimally in this way.

illustration image
  • Initially, we have put the time as zero.
  • Person-1 and person-2 cross the bridge together, taking the torch with them. Time is 2 minutes as they move at the slower person’s pace.
  • Person-1 returns with the torch. It takes 1 minute time.
  • Person-10 and person-5 cross the bridge together with the torch. It takes 10 minutes.
  • Person-2 returns with the torch as he is the fastest among those who have crossed the bridge. It takes 2 minutes.
  • Person-1 and person-2 cross the bridge together with the torch. It takes 2 minutes to cross them.

The total time taken in this case is 17 minutes. So it takes 17 minutes minimum to cross the bridge.

You can try different approaches. You will find that this is the least possible time to cross the bridge.

Frequently Asked Questions

Why don’t we send everyone across the bridge in one go as it will take 10 minutes only?

There is a constraint in the puzzle that a maximum of 2 people can cross the bridge at once.

When the 10-minute person and 1-minute person cross the bridge, why do we take the final time as 10 minutes?

We take the total time as 10 minutes because they have to travel together to see the torchlight.

Do I need to memorize all the puzzles?

No, when you try solving a puzzle yourself, it gets stuck in your memory for a long time as you have struggled to solve it. Even if you couldn’t solve it yourself, you won’t forget it for a long time as you realize the mistakes you made while solving it.

Why are puzzles important?

Puzzles enhance your ability to think. It also improves your problem-solving skills. You will have to apply your mind to solve a puzzle, so it’s also a good exercise for the mind. You will improve your logical thinking and reasoning ability by solving puzzles.

Are puzzles asked in the interview of IT companies?

Many tech giants like Google, Microsoft, etc., ask the puzzles in the interview process as they want to check your logical thinking.

Conclusion

We have extensively discussed the cross-the-bridge puzzle.

Logical Puzzles:


Pattern Based Puzzles:


Recommended Readings:


Check out some of the amazing Guided Paths on topics such as Interview Puzzles, Data Structure and Algorithms, Competitive Programming, Basics of C, Basics of Java, Computer Networks, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Happy Learning!!!

Previous article
Ten Black and Ten White Socks
Next article
Wizards and the Dwarves
Live masterclass