Interview Question
Country: United States
Lets say 4 persons A, B,C & D
A= 1 Min.
B= 2 min.
C= 5min,
D = 10 mins.
1. first A & B will go , A will return total time 1+2= 3 min.B will be stay there.
2. C & D will go together, B will return now. Total time D+B = 10 +2 = 12 Min.
3. Finally A& B will go together , total time 2 min.
So total time to cross bridge is 3+12+2 = 17 Min
Hey guys. Finding the solution to this specific problem is not a big deal, what is interesting here is the algorithm, especially when considering the number of people grows. Can you generalize and scale the algorithm - I think this is what actually the problem setter wants to see here. For example, how would yoou go with the series like: 1, 2, 5, 10, 12, 16, 20, 22, etc ?
There is no reason to extrapolate and assume that this is what the problem setter wants. The 17-minute puzzle is a classic problem.
Suppose there are four person named as a,b,c,d , which take 1,2,5,10 minutes to cross the bridge.
- Gupta June 18, 20121)first 'A' and 'B' cross the bridge and 'A' will come back again at original side , it will take total of 3 minutes (2+1).
2) now 'C' and 'D' cross the bridge and 'B' will come back again at original side with flash light.it will take total of 12 minutes (10 + 2)
3) Finally 'A' and 'B' cross the bridge with flash light and no need to come back again at original side. because all four are at other side of bridge. this step will take 2 minute.
So total tike taken is 3 + 12+ 2 => 17 minutes.
Let me know if more clarity requires.