Bloomberg LP Interview Question Financial Software Developers
If back trip need to come two. they can't make this. it will infinite loop. back and forth. :)
A follow up problem: given N people with times Ti (for 1 <= i <= n) to cross the bridge, how to get optimum crossover time?
Seems a greedy approach by moving two slowest persons at each stage (in some optimal way) would be overall optimal solution. Any idea?
No it won't. The optimal solution is to use the fastest person to escort the others. It will minimize the time to bring the flashlight back and forth.
@Anthony: your approach is NOT correct always. It depends on the Ti values.
For N = 4, and T1 = 1, T2= 2, T3 = 5, T4 = 10. Your technique gives:
1st trip : max (T1, T4) = 10
T1 back : = 1
2nd trip : max (T1, T3) = 5
T1 back : = 1
3rd trip : max (T1, T2) = 2
Total : 19, where as optimal 17
it's not correct. What if a = 1, b = 4, c = 5, d = 10?
your equation gives 23, whereas optimal is 10 + 1 + 5 + 1 + 4 = 21
Case 1: IF the question restricts that only one pair can travel over the bridge at a time, then its not solvable.. Consider any pair, if they cross from one side to other, while coming back, again they have to travel in pair, so at the end of one to-fro, u will again have 4 pple on the same bank..
Case 2: IF they can travel in multiple pairs, then the shortest time would be when they all travel together (i.e. 2 pairs of pple, i.e. 4).. Since all are traveling together, simultaneously, max time would be 10 mins, i.e. max time taken by slowest of them all, i.e. d..
(Think logically before jumping off to solutions)
The person who posted the question either is lazy or careless. He left important portions of problem statements out: it's a nighttime activity, so they need to use the flashlight (only one avaliable), and the bridge can support up to two people (so people can cross the bridge either alone or in pair).
In this..for say N people, intially sort the people acc to their time in ascend.
Now #1 will be the retriver (of light) and #2 will be escorter to only the retriever.
Step 1: Escorter takes the retriver and brings himself back with light.
Step2: N (highest time) and N-1 (second highest) go together and retriever comes with light. (Now delete from the array , N and N-1)
Step 3: repeat step 1
Step 4: Find new N and N-1 Repeat step 2...continue untill N=escorter.
End
That algo does not work for obvious reasons.
Here is the algo works:
1. Find two min weights on side-A (or sort them in order, pick up two lease number)
2. Send them to other side-B, put them in sort order
3. Select min on Side-B (or first element), bring them back to Side-A
4. Now, select two max weights on side-A, send them to Side-B
5. Find min of side-B, bring back to side-A
6. Repeat 1 to 4 until side-A is empty.
This works, because we are altering the min and max on side-A, also always min on side-B for optimization. Let me know if any one thinks this logic does not work.
From my perspective the main point is that they have to move in pairs, in order to cross the bridge, so first pair C & D (10 min), then after them A & B (2 min) will cross. Total time 12 min.
They do not say that they need the flashlight in order to cross the bridge, so they do not have to come back to give the flashlight back, and they are always in pairs.
Here is a solution in 11.6 minutes:
c and d start crossing together, d holds the flashlight
after 5 minutes, c finished crossing. d stops and points the flashlight towards b. b starts crossing. after 1 minute, b reaches d. d flips the flashlight and starts moving (b continues to move).
after another minute, when b finished crossing, d is at 60% (and 5+1+1=7 minutes have passed). d stops and flips the flashlight towards a, and a starts to cross. after 0.6 minutes, a reaches d. d flips the flashlight again.and starts moving. at this point d is at 60% of the bridge and 7.6 minutes have passed. In another 4 minutes d crosses the entire bridge, for a total of 11.6 minutes.
This was, there are no more than 2 people on the bridge at any given time and everyone has his path illuminated.
Answer is 10 minutes.
Explanation
Person a = 1 min
Person b = 2 min
Person c = 5 min
Person d = 10 min
1) Person d & Person c with Person d having the light. C will reach in 5 minutes and D will reach half way.
2) Once the person C reaches the other end Person B starts and will reach in 2 minutes.
3) Finally Person A will start and reach in 1 minute
a&b 2
- Anonymous May 09, 2011b 2
c&d 10
a 1
a&b 2
total:17