← Uber Interview InsightsMachine Learning Engineer

Uber·Machine Learning Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say
Jun 2026Remote

Summary

Uber MLE interview with a graph/BFS problem that looks deceptively straightforward until you actually try to implement it efficiently. Not the worst experience but definitely left me second-guessing my approach the whole way through.

Questions Asked (1)

Q1

Given an array of bus routes where each route loops forever, find the minimum number of buses you need to take to get from a source stop to a target stop. Return -1 if it's impossible.

Algorithms & Data Structures
Author's notes

My first instinct was plain BFS on stops, which is wrong because the search space explodes.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a graph where each bus route is a node, and edges exist between routes that share at least one stop. Then perform BFS from all routes containing the source stop to find the minimum number of buses to reach any route containing the target stop. If source and target are the same stop, return 0; if no path exists, return -1.

Pro tip: Clarify upfront that if the source and target stops are identical, the answer is 0, and if either stop is not in any route, return -1. This shows attention to edge cases and prevents miscommunication.

1. Clarify the problem and edge cases

Confirm that buses loop forever, so you can board any bus at any stop it serves. Discuss edge cases: source equals target (return 0), source or target not in any route (return -1), and multiple routes containing the same stop.

2. Model as a graph of bus routes

Treat each bus route as a node. Connect two routes with an edge if they share at least one stop. This transforms the problem into finding the shortest path in an unweighted graph, where each edge represents taking one additional bus.

3. Build the graph efficiently

Use a hash map to map each stop to the list of routes that include it. Then, for each stop, connect all routes that share that stop. This avoids O(R^2 * S) comparisons and achieves O(total stops across routes) time.

4. Run BFS from source routes to target routes

Initialize a queue with all routes containing the source stop (each counts as 1 bus). Perform BFS, tracking visited routes. When you encounter a route containing the target stop, return the current bus count. If the queue empties without reaching the target, return -1.

5. Analyze complexity and discuss optimizations

State that time complexity is O(N) where N is total number of stops across all routes, and space is O(N) for the graph and visited set. Mention that bidirectional BFS or early termination can optimize further.

Key Points to Mention

  • Graph modeling: routes as nodes, shared stops as edges
  • BFS for shortest path in unweighted graph
  • Handling edge cases: source == target, unreachable stops
  • Efficient graph construction using stop-to-routes mapping
  • Time and space complexity analysis
  • Potential optimizations: bidirectional BFS, early exit

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