← Uber Interview Insights

Uber·Frontend Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Uber frontend interview that threw a graph problem at me, which felt a bit out of left field for the role. Not a ton of context around the round itself but the problem was meaty enough to remember.

Questions Asked (1)

Q1

Given a list of flights with source, destination, and cost, find the cheapest route between two cities using at most k stops. Return -1 if no route exists.

Algorithms & Data Structures
Author's notes

Classic shortest path with a constraint, which meant vanilla Dijkstra wasn't quite right.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the flights as a weighted directed graph and use a modified BFS (level-order traversal) to find the cheapest path within k stops, tracking the minimum cost to each city at each stop level. Alternatively, use Bellman-Ford with at most k+1 edges, relaxing edges iteratively while preventing updates within the same iteration to respect the stop limit.

Pro tip: Clarify edge cases upfront: whether k stops means k intermediate cities or k flights, and if multiple flights between same cities exist. Also, mention that BFS with priority queue (Dijkstra) fails because it doesn't account for stop limit, so a level-based approach is necessary.

1. Clarify the problem

Ask clarifying questions: Does 'at most k stops' mean k intermediate cities (so k+1 flights) or k flights? Are costs positive? Can there be multiple flights between same cities? What if source equals destination?

2. Choose the right algorithm

Explain that BFS with level tracking or Bellman-Ford with edge limit is suitable. Mention that Dijkstra's algorithm doesn't work directly because it doesn't handle the stop constraint.

3. Outline the solution

Describe the steps: build adjacency list, initialize cost array with infinity, set cost[source]=0, then for each stop level (0 to k), relax all edges from current level to next level, updating costs only if cheaper. Return cost[destination] or -1.

4. Analyze complexity

State time complexity: O(k * E) where E is number of flights, or O(V * E) for Bellman-Ford. Space complexity: O(V) for cost array and queue.

5. Test with examples

Walk through a simple example, including edge cases like no route, source equals destination, and exactly k stops. Verify the algorithm handles them correctly.

Key Points to Mention

  • Graph representation: adjacency list with (destination, cost) pairs.
  • BFS level-order traversal to track number of stops.
  • Bellman-Ford relaxation with a copy of costs to avoid using updated values in the same iteration.
  • Handling of multiple flights between same cities by keeping the minimum cost.
  • Edge cases: no route, source equals destination, k=0 (direct flight only), negative costs (if allowed).
  • Time and space complexity analysis.

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