Fuel Route with Fewest Station Visits
Google● HardFULLTIMEONSITE INTERVIEWProblem statement
There are n cities numbered 0 to n - 1. Each entry [u, v] in roads is a two-way road that directly connects two different cities. Driving along one road, in either direction, uses exactly 1 kg of fuel.
A car starts in city source with fuel kg of fuel and wants to reach city destination. The cities listed in stations have a refueling station. Whenever the car arrives at a station city, it must refuel to exactly fuel kg. The source city is never a station.
Examples
Example 1
n = 5roads = [[0,1],[1,4],[0,2],[2,3],[3,4]]fuel = 3source = 0destination = 4stations = [1]return = [0,3]The route 0 → 1 → 4 uses only 2 roads, but city 1 is a station, so it costs one station visit.
The route 0 → 2 → 3 → 4 uses 3 roads and no stations. The fuel goes 3 → 2 → 1 → 0, so it never drops below 0. Fewer stations matter more than fewer roads, so the answer is [0,3].
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 2 more worked examples, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.