How far into the desert with two tanks of fuel?
A jeep can carry one tank of fuel, enough to drive exactly 500 km. At the base camp there are exactly two tanks' worth of fuel in total. The jeep may drive out, leave any amount of fuel in cans in the sand, return, refuel, and set out again. The goal is to reach as far as possible into the desert on a one-way trip; the jeep does not need to come back at the end.
What is the maximum distance from base the jeep can reach?
Show a hint
With one tank you get 500 km. The second tank cannot be carried along, but part of it can be carried out, dropped, and picked up later. Where should the cache be so that the final trip sets off from the cache with a completely full tank?
Your answer
Solving needs a free account
Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.
Discussion
💡 Discussion rules
- No full solutions here. Hints and approaches only.
- Complexity, edge cases and intuition are the point.
- Interview experiences are welcome. Respect your NDAs.
Loading discussion…
Learn the concepts
The theory behind this question.