Uber·Machine Learning Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jul 2026

Summary

Uber MLE interview with a graph/BFS problem that looks deceptively clean on the surface. The bus routes question took me longer than I expected to untangle.

Questions Asked (1)

You're given a list of bus routes, where each route is a circular sequence of stops a bus repeats indefinitely. Starting at a given stop, find the minimum number of buses you need to board to reach a target stop. Return -1 if it's unreachable.

Algorithms & Data Structures

Author's notes

My first instinct was Dijkstra and that was the wrong direction to go down.

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 start stop to find the minimum number of buses to reach any route containing the target stop. If start equals target, return 0; if no such route exists, return -1.

Pro tip: Clarify upfront that boarding a bus counts as one, so the answer is the number of buses boarded, not the number of transfers. Also, mention that if the start and target stops are the same, the answer is 0, which is a common edge case.

1. Clarify and handle edge cases

Confirm that the start and target stops are distinct and that each bus route is circular. If start equals target, return 0 immediately.

2. Build stop-to-route mapping

Create a hash map from each stop to the list of routes that include it. This allows quick lookup of which buses can be boarded at any stop.

3. Construct route graph

For each pair of routes that share at least one stop, add an undirected edge. This graph represents which buses can be transferred between.

4. BFS from start routes

Initialize a queue with all routes containing the start stop, marking them visited with distance 1. Perform BFS, and when a route containing the target stop is dequeued, return its distance.

5. Return result

If BFS exhausts all reachable routes without finding the target, return -1. Otherwise, the BFS distance gives the minimum number of buses needed.

Key Points to Mention

Graph modeling: routes as nodes, shared stops as edges.
BFS guarantees minimum number of buses because each edge represents boarding one additional bus.
Time complexity: O(N * S + N^2) where N is number of routes and S is average stops per route, but can be optimized.
Space complexity: O(N + total stops) for the graph and stop-to-route map.
Edge case: start equals target returns 0.
Optimization: Instead of building full route graph, BFS can be done on the fly by exploring routes sharing stops with current routes, using a visited set for routes and stops.

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