Question Details
Problem
You start at position 0 on a number line with a full tank of fuel units. There are n stations at given positions, each with a certain amount of additional fuel. You can stop at any subset of stations.
Return the furthest position you can reach.
python
def furthest_distance(
stations: list[tuple[int, int]], # (position, fuel_available)
initial_fuel: int
) -> int:
pass
**Input**: stations = [(10, 60), (20, 30), (30, 40), (60, 50)], initial_fuel = 40
Output: 70
# Reach station at 10 (use 10 fuel, pick up 60) -> tank=90
# Reach station at 20 (use 10, pick up 30) -> tank=110
# Reach station at 30 (use 10, pick up 40) -> tank=140
# Reach 70 (use 40) -> stops here, tank=100... actually can reach further
# Max is 70 without overshoot logic; trace carefully.
**Input**: stations = [(5, 10)], initial_fuel = 3
Output: 3
# Cannot reach any station, stop at 3
Follow-ups
- How does a greedy approach with a max-heap of
passed stations help here?
2. What is the time complexity of your solution?
3. How would you track which stations were actually visited?
4. If there is a destination D you must reach exactly, how does the problem change?
Full Details
Problem
You start at position 0 on a number line with a full tank of fuel units. There are n stations at given positions, each with a certain amount of additional fuel. You can stop at any subset of stations.
Return the furthest position you can reach.
python
def furthest_distance(
stations: list[tuple[int, int]], # (position, fuel_available)
initial_fuel: int
) -> int:
pass
**Input**: stations = [(10, 60), (20, 30), (30, 40), (60, 50)], initial_fuel = 40
Output: 70
# Reach station at 10 (use 10 fuel, pick up 60) -> tank=90
# Reach station at 20 (use 10, pick up 30) -> tank=110
# Reach station at 30 (use 10, pick up 40) -> tank=140
# Reach 70 (use 40) -> stops here, tank=100... actually can reach further
# Max is 70 without overshoot logic; trace carefully.
**Input**: stations = [(5, 10)], initial_fuel = 3
Output: 3
# Cannot reach any station, stop at 3
Follow-ups
- How does a greedy approach with a max-heap of
passed stations help here?
2. What is the time complexity of your solution?
3. How would you track which stations were actually visited?
4. If there is a destination D you must reach exactly, how does the problem change?
About This Question
This is a reported interview question from a ziphq interview during the phone round.
It covers the following topics: Heap, Phone, Greedy, Coding, Onsite .