DSA interview question

Cheapest Flights Within K Stops

Hard · Algorithms · Topics: graph, bellman ford, dp

The problem

A travel site searches for the cheapest itinerary from city src to city dst using at most k stops (so at most k + 1 flights). Plain Dijkstra optimises cost alone and can pick a cheap route with too many stops. The clean solution is Bellman–Ford limited to k + 1 rounds. After round i, dist[v] is the cheapest cost using at most i flights. Each round must relax from a copy of the previous round's distances, so a single round can't chain several flights together.

Example: 4 cities, flights 0→1 (100), 1→2 (100), 2→0 (100), 1→3 (600), 2→3 (200), src 0, dst 3, k = 1 → 700.

Function signature

int findCheapestPrice(int n, const vector<array<int, 3>>& flights, int src, int dst, int k);  // -1 if impossible

Test cases

Input `(n, flights, src, dst, k)`	Output	Explanation
`(4, [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], 0, 3, 1)`	`700`	0-1-3; the cheaper 0-1-2-3 needs 2 stops
`(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1)`	`200`
`(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0)`	`500`	No stops: direct only
`(3, [[0,1,100]], 0, 2, 1)`	`-1`	No route
`(2, [[0,1,5]], 0, 1, 0)`	`5`

(Confirm: flights are directed with positive prices; "k stops" means at most k + 1 flights.)

How interviewers phrase it

"Find the cheapest price from src to dst with at most k stops; if there is no such route, return −1" (LeetCode 787).

Clarifying questions to ask

Does k count intermediate cities or flights? (Intermediate stops, so k + 1 flights.)
Are prices positive? (Yes.)
How large? (n ≤ 100 cities, so O(k · E) is fine.)

Follow-ups to expect

"Why not plain Dijkstra?"
"Why copy the distances each round?"
"BFS alternative?"
"What happens to cycles?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview