Problem overview

You are given a directed, weighted graph of cities (flights as [u, v, price]). The task is to compute the minimum cost to travel from a source city to a destination city using at most k stops (intermediate cities). If no route satisfies the stop constraint, return -1. Remember: 0 stops means a direct flight (one edge), so allowed edges <= k + 1.

What you'll be asked to do

You should clarify input ranges and edge cases, then choose and justify an algorithm. Interviewers expect you to implement a correct, efficient solution that respects the stops constraint and to reason about time/space trade-offs.

Common approaches (what to discuss and why)

• Modified Dijkstra / priority queue over states (node, stops remaining): you push states with accumulated cost and remaining stops and pop the smallest cost first. This gives fast pruning but you must track visited states by stops to avoid discarding valid paths.

• BFS layered by number of stops (or level-by-level relaxation): treat each BFS level as one additional stop and keep best costs per node per level; good for small k.

• Bellman–Ford style DP relaxing edges exactly k+1 times: set dp[t][v] = min cost to reach v using ≤ t edges (t from 0..k+1). This is simple and predictable: O(k * E) time.

Flow in an interview

1. Restate the problem and confirm how stops are counted.
2. Walk through a small example and edge cases (no path, src==dst, k>=n).
3. Propose a solution (explain choice), write pseudocode/implementation, and test with examples.
4. Discuss complexity, optimizations, and alternative approaches.

Skill signals the interviewer is assessing

You should demonstrate: graph modeling, priority queues or DP arrays, time/space complexity reasoning, state pruning (tracking best cost per node per stops), handling edge cases, and writing clean, testable code. Mention trade-offs: Dijkstra-like approach is faster in practice; Bellman–Ford is easier to reason about for the stops limit.

Interview tips

Clarify constraints (n, E, price ranges). If k is large (≥ n), you can relax the stop constraint. Use a dist table sized by node × (k+2) or keep best-known cost per (node, stops) to avoid revisiting useless states. Test with direct, unreachable, and multi-path examples.