Coding · Heaps
Fewest Energy Drinks to Finish a Marathon
- Reported once
- Hard
- SDE-2
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
A runner starts a marathon with reserve calories of energy and burns perMile calories for every mile. Along the course there are checkpoints, and each one holds a single energy drink worth a known number of calories. The array gaps lists the miles from the start to the first checkpoint, then between each pair of checkpoints, then from the last checkpoint to the finish, so it has one more entry than the array drinks. The runner may take a drink only at a checkpoint that has been reached, takes the whole drink, and must never run out of energy before reaching the next point, although arriving with exactly zero is fine. Return the fewest drinks that get the runner to the finish, or -1 if it cannot be done. For reserve 10, perMile 1, gaps [10,10,10,30,40] and drinks [60,30,30,40] the answer is 2. There are up to 100,000 checkpoints.
Restated in our own words, not a quote from Flipkart or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
The candidate report describes this problem only loosely: an athlete with a reserve, a burn per mile, and checkpoints holding drinks, with gaps between them. The report also says the candidate got stuck and needed a hint. Its sample lists as many distances as drinks, so it does not say whether a first leg from the start to the first checkpoint exists. I would not guess the statement. I would fix an interpretation out loud and confirm it, and this answer solves the one in the prompt above, where the first and last legs both count. It has the same shape as the well known minimum refuelling stops problem but is not that exact statement.
Choices to confirm: each checkpoint holds one drink and the runner takes all of it or none, there is no limit on how much energy the runner can hold, energy does not decay, arriving at a point with exactly zero is allowed, and when the finish cannot be reached the answer is -1.
Brute force
Say the obvious answer and why it is too slow.
Try every subset of checkpoints to drink at. For each subset, simulate the run, subtract the burn on every leg, add the drink at each chosen checkpoint, and fail if the energy ever drops below zero before a point. Keep the smallest feasible subset. That is 2n subsets with an O(n) simulation each, hopeless at 100,000 checkpoints.
A table is the middle step: let best[j] be the largest total energy gathered using j drinks among the checkpoints seen so far, keeping only choices that never ran dry. It runs in O(n²), which is still too slow at this size. The table spends effort on every count j at every checkpoint, while the question needs only the smallest j.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(2^n × n)
- Time
- O(n log n)
- Space
- O(n)
The pattern is greedy with a max-heap, a lazy choice made at the last possible moment. Do not decide at a checkpoint whether to drink. Just remember what was on offer. Push each drink into a max-heap as soon as it is passed. Run the legs in order. If the energy in hand does not cover the next leg, the runner would stall, so reach back and drink the largest drink passed so far: pop it, add it to the energy, and count it. Repeat until the leg is covered. If the heap is empty while the energy is still short, no drink could have helped and the answer is -1.
Why may we drink retroactively? Energy never expires and extra energy never hurts an earlier leg, so taking a passed drink late gives the same result as taking it on the spot. A drink is worth taking only when it prevents a stall, so we delay every choice until a stall forces one.
Why the largest one? Assume an optimal plan that contains every drink we have taken so far. At a stall, those drinks are not enough, so the plan must hold another drink y passed before the stall, and y is no larger than the largest passed drink we have not taken, call it x. If the plan lacks x, swap y for x. Every leg before the stall was already covered by the drinks we took earlier, which the plan still holds, and from the stall onward the plan has at least as much energy as before. So the swapped plan is no worse, the greedy choice is safe, and repeating the argument shows the greedy count is the smallest. A stall with an empty heap means every passed drink is already taken, so the point is unreachable.
Out loud: "I carry every drink I have passed in a max-heap and only reach for one when I would run dry, always the biggest."
Walk it through
A dry run on the example, step by step.
| Leg | Burn | Energy at start | Drink taken | Left | Heap after |
|---|---|---|---|---|---|
| 1 | 10 | 10 | - | 0 | 60 |
| 2 | 10 | 0 | 60 | 50 | 30 |
| 3 | 10 | 50 | - | 40 | 30,30 |
| 4 | 30 | 40 | - | 10 | 40,30,30 |
| 5 | 40 | 10 | 40 | 10 | 30,30 |
Take reserve 10, one calorie per mile, gaps [10,10,10,30,40] and drinks [60,30,30,40]. Leg 1 burns 10, the runner has exactly 10, arrives with 0, and the 60 drink joins the heap. Leg 2 burns 10 with nothing in hand, so it stalls: pop 60, count 1, energy 60, then 50 left after the leg, and the first 30 joins the heap.
Leg 3 burns 10, leaving 40, and the second 30 joins. Leg 4 burns 30, leaving 10, and 40 joins. The last leg to the finish burns 40 with 10 in hand, so it stalls again: pop 40, count 2, energy 50, and 10 is left at the finish. The answer is 2.
The code
Runnable JavaScript, checked against test cases.
class MaxHeap {
constructor() {
this.items = [];
}
get size() {
return this.items.length;
}
push(value) {
const items = this.items;
items.push(value);
let child = items.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (items[parent] >= items[child]) break;
[items[parent], items[child]] = [items[child], items[parent]];
child = parent;
}
}
pop() {
const items = this.items;
const top = items[0];
const last = items.pop();
if (items.length > 0) {
items[0] = last;
let parent = 0;
for (;;) {
const left = 2 * parent + 1;
const right = left + 1;
let largest = parent;
if (left < items.length && items[left] > items[largest]) largest = left;
if (right < items.length && items[right] > items[largest]) largest = right;
if (largest === parent) break;
[items[parent], items[largest]] = [items[largest], items[parent]];
parent = largest;
}
}
return top;
}
}
function fewestDrinks(reserve, perMile, gaps, drinks) {
const passed = new MaxHeap();
let energy = reserve;
let taken = 0;
for (let leg = 0; leg < gaps.length; leg++) {
const burn = gaps[leg] * perMile;
while (energy < burn) {
if (passed.size === 0) return -1;
energy += passed.pop();
taken++;
}
energy -= burn;
if (leg < drinks.length) passed.push(drinks[leg]);
}
return taken;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
No checkpoints: there is a single leg. The answer is 0 if the reserve covers it and -1 otherwise.
- Reserve already enough: no stall ever happens, so no drink is taken and the answer is 0.
- Arriving with exactly zero: allowed, so the stall test is energy below burn, never at or below it.
- Stall on the first leg: the heap is empty, so the answer is -1.
- Drinks worth zero: they are popped only after everything larger is gone, when the run is already doomed, so they never change a successful answer.
- Burn rate of zero or gaps of zero: nothing is burned, so no stall can occur.
- Equal drinks: ties in the heap do not matter.
Follow-ups to expect
Where the interviewer pushes next.
- How would the answer change if the runner can hold at most a fixed amount of energy, so a drink can be wasted?
- How would you return which checkpoints the drinks were taken at?
- How would you solve it if each drink had a cost and you wanted the cheapest plan instead of the fewest drinks?
- How would you process checkpoints as a stream if the course is not known in advance?
Where candidates slip
The mistakes this problem punishes.
The common slip is deciding at each checkpoint, for example always drinking, or drinking only when the next leg looks long. The choice cannot be made correctly until a stall shows that it is needed.
- Sorting all drinks and taking the largest overall, which ignores that a drink must be passed before it can be used.
- Pushing a checkpoint's drink into the heap before the leg that reaches that checkpoint.
- Skipping the final leg from the last checkpoint to the finish, so the run is never checked there.
- Stalling when energy is at or below the burn, which rejects exact arrival with zero.
- Taking only one drink per stall instead of looping until the leg is covered.
- Popping from an empty heap instead of returning -1.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.