Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Uber SWE interview with a graph problem that looks like a classic shortest path but has a constraint that changes everything. Not a bad experience, just needed to think more carefully before jumping to Dijkstra.

Questions Asked (1)

Given a directed weighted graph of flights between cities, find the cheapest route from a source city to a destination city using at most K stops. Return -1 if no valid route exists.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was Dijkstra and I started going down that road before realizing the K-stops constraint breaks the usual greedy logic.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the flights as a directed weighted graph and use a modified BFS (level-by-level) to track the minimum cost to each city within a given number of stops. Since we need the cheapest route with at most K stops, we can use Bellman-Ford with K+1 iterations or a priority queue with state (city, stops, cost).

Pro tip: Clarify whether 'at most K stops' means K intermediate cities or K edges; this distinction affects the algorithm's stopping condition and is a common source of off-by-one errors.

1. Clarify the problem

Confirm the definition of a 'stop' (intermediate city vs. edge) and whether the graph can have cycles or negative weights. Also, ask about constraints on K and graph size to choose the optimal algorithm.

2. Choose the algorithm

Decide between BFS with level tracking, Bellman-Ford with K+1 iterations, or Dijkstra with a modified state. Explain the trade-offs: BFS is simple but may revisit nodes; Bellman-Ford handles negative weights but is slower; Dijkstra with state is efficient for non-negative weights.

3. Define the state and transitions

For BFS/Bellman-Ford, maintain an array of minimum costs to each city for the current number of stops. For Dijkstra, use a priority queue of (cost, city, stops) and update if a cheaper cost is found with fewer or equal stops.

4. Implement and handle edge cases

Code the chosen algorithm, ensuring to return -1 if the destination is unreachable within K stops. Handle cases where source equals destination (cost 0) and when K is 0 (only direct flights allowed).

5. Analyze complexity and test

State the time and space complexity (e.g., O(K * E) for Bellman-Ford, O(E log V) for Dijkstra with state). Walk through a small example to verify correctness and discuss potential optimizations.

Key Points to Mention

Graph representation: adjacency list is typically more efficient for sparse graphs.
Bellman-Ford relaxation: iterate K+1 times, using a copy of distances to avoid using updated values in the same iteration.
BFS with level tracking: process nodes level by level, where each level corresponds to one additional stop.
Dijkstra with state: priority queue ordered by cost, but need to track stops to enforce the K constraint.
Edge cases: no path, source equals destination, K=0, negative weight cycles (if allowed).
Time and space complexity: compare approaches and justify the chosen one based on constraints.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.