Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Uber SWE interview with a graph BFS problem that looks deceptively simple until you realize the naive stop-by-stop BFS will TLE you into oblivion. The key insight is modeling the problem over buses rather than stops, and I didn't get there fast enough on my own.

Questions Asked (1)

Given an array of bus routes where each route cycles through a list of stops forever, find the minimum number of buses you need to take to travel from a source stop to a target stop. Return -1 if it's not reachable.

Algorithms & Data Structures

Author's notes

My first instinct was BFS over stops, which is the wrong layer of abstraction.

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 there is an edge between two routes if they share a common stop. Then perform BFS from all routes containing the source stop to find the minimum number of routes (buses) needed to reach any route containing the target stop. If the source and target are the same stop, return 0; if no path exists, return -1.

Pro tip: Clarify that you're counting buses (routes taken), not stops, and handle the edge case where source equals target upfront. Also, mention that precomputing stop-to-routes mapping optimizes the BFS.

1. Clarify and define the problem

Confirm that each bus route is a cycle and you can transfer between routes at shared stops. The goal is to minimize the number of buses taken, i.e., the number of routes used.

2. Build the graph representation

Create a mapping from each stop to the list of routes that include it. Also, represent each route as a node, and add edges between routes that share at least one stop.

3. Run BFS from source routes

Initialize a queue with all routes containing the source stop, marking them as visited with distance 1. Perform BFS, exploring neighboring routes (those sharing a stop) and incrementing distance by 1 for each new route.

4. Check for target and return result

During BFS, if you encounter a route that contains the target stop, return the current distance. If the queue is exhausted without finding the target, return -1.

5. Handle edge cases

If source equals target, return 0 immediately. Also, consider if source or target is not in any route, return -1.

Key Points to Mention

Graph modeling: routes as nodes, edges when routes share a stop.
BFS for shortest path in unweighted graph (minimum number of buses).
Preprocessing: stop-to-routes mapping to efficiently find neighbors.
Time and space complexity: O(N*M) where N is number of routes and M is average stops per route, or O(total stops) for preprocessing.
Edge cases: source == target, unreachable target, source/target not in any route.
Alternative approach: BFS on stops with route tracking, but route-based BFS is more efficient.

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