Possible flight routes
SQL data engineering interview problem. Difficulty: advanced. Pattern: CTEs. About 20 minutes. Part of the Pro drill bank.
flights lists direct airline segments with columns flight_id, origin, destination, and cost. Find all possible flight routes between any two cities with at most one intermediate stop (0 stops or 1 stop), without cycles (a flight cannot revisit its origin city). For each origin and destination pair with at least one valid route, return the cheapest fare (cheapest_cost) and the number of stops on that cheapest itinerary. If a direct flight and a 1-stop flight tie on cost, choose the flight with fewer stops. Order by origin ascending, then destination ascending.
Requirements
- Output columns: origin, destination, cheapest_cost, stops.
- Order by origin ascending, destination ascending.
Constraints
- cost is positive.
- Routes have at most 1 stop (maximum 2 flight segments).
- No route may have origin equal to destination.
Examples
Input: flights flight_id,origin,destination,cost F1,DEL,BOM,4000 F2,DEL,BLR,6000 F3,BOM,BLR,2500 F4,BLR,HYD,2000 F5,DEL,HYD,7000 Output: origin | destination | cheapest_cost | stops BLR | HYD | 2000 | 0 BOM | BLR | 2500 | 0 BOM | HYD | 4500 | 1 DEL | BLR | 6000 | 0 DEL | BOM | 4000 | 0 DEL | HYD | 7000 | 0 Why this passes: DEL to BOM costs 4000 and BOM to BLR costs 2500, so DEL to BLR can be 6500 via BOM, but the direct flight at 6000 is cheaper and kept; BOM to HYD only exists as BOM to BLR to HYD, which costs 4500 and has 1 stop.
Input: flights flight_id | origin | destination | cost 1 | X | Y | 50 Output: origin | destination | cheapest_cost | stops X | Y | 50 | 0 Why this passes: Only direct route exists.
Topics: lakebench, sql, self-join, paths.
More SQL interview questions · All interview problems · Learn data engineering
Possible flight routes
Interview-style drill: Determine all valid non-stop and one-stop flight itineraries and find the minimum fare for every city pair.
`flights` lists direct airline segments with columns `flight_id`, `origin`, `destination`, and `cost`. Find all possible flight routes between any two cities with at most one intermediate stop (0 stops or 1 stop), without cycles (a flight cannot revisit its origin city). For each origin and destination pair with at least one valid route, return the cheapest fare (`cheapest_cost`) and the number of `stops` on that cheapest itinerary. If a direct flight and a 1-stop flight tie on cost, choose the flight with fewer stops. Order by `origin` ascending, then `destination` ascending.