VLSI DV Interview Puzzles · All levels
Bridge and Torch (1, 2, 7, 10 Minutes)
Four people need to cross a bridge at night with one torch. At most two cross at once; pair speed is slower person's time. Times are 1, 2, 7, 10 minutes. Minimize total time.
Puzzle
Difficulty: Hard · Puzzle 5 of 6 · Topic: Classic Brain Teasers
Four people need to cross a bridge at night with one torch. At most two cross at once; pair speed is slower person's time. Times are 1, 2, 7, 10 minutes. Minimize total time.
Hint
Compare two strategies for moving the two slowest across.
Step-by-step solution
diagram
1) Optimal pattern uses two fastest as shuttles.
2) Send 1 and 2 across: +2.
3) Send 1 back: +1 (total 3).
4) Send 7 and 10 across together: +10 (total 13).
5) Send 2 back: +2 (total 15).
6) Send 1 and 2 across: +2 (total 17).
7) Alternate strategy (1 with each slow person) costs 19, so 17 is minimum.Answer
Answer: Minimum total crossing time is 17 minutes.
Why candidates get it wrong
Greedy 'always send fastest with slowest' gives 19 and misses global optimum.
Interviewer follow-up
For times 1, 2, 5, 10, what is the optimal total and why?