Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Uber SWE interview with a graph problem that looked manageable until I actually had to implement it cleanly under pressure. The optimal path requires sorting both queries and edges, then running union-find incrementally, and there are enough moving parts that small bugs will kill you.

Questions Asked (1)

Given an undirected weighted graph and a list of queries each specifying two nodes and a weight limit, determine for each query whether a path exists between the two nodes using only edges with weight strictly less than the given limit.

Algorithms & Data Structures

Author's notes

The naive approach of running a fresh BFS per query will time out.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Sort the edges by weight and process queries offline in increasing order of weight limit, using a Union-Find (Disjoint Set Union) data structure to incrementally add edges that satisfy the weight constraint. For each query, after adding all edges with weight < limit, check if the two nodes are in the same connected component. This yields near-linear time complexity.

Pro tip: Mention that offline processing with sorting and DSU is optimal for this problem, and briefly compare it to online approaches like binary search on a minimum spanning tree or Kruskal reconstruction tree, showing awareness of trade-offs.

1. Understand the problem and constraints

Clarify that edges with weight strictly less than the limit are allowed, and that queries are independent. Discuss input size to choose an efficient algorithm.

2. Choose the right data structure

Select Union-Find (Disjoint Set Union) with path compression and union by rank/size to efficiently maintain connected components as edges are added.

3. Process queries offline

Sort edges by weight and queries by weight limit. Iterate through queries in increasing limit order, adding all edges with weight < limit to the DSU.

4. Answer each query

For each query, after adding the eligible edges, check if the two nodes belong to the same component using find operations.

5. Analyze complexity and edge cases

State time complexity O((E + Q) log E) due to sorting, and space O(V + E). Handle cases like no edges, disconnected nodes, and equal weights.

Key Points to Mention

Union-Find (Disjoint Set Union) with path compression and union by rank for near-constant time operations.
Offline processing: sorting queries by weight limit to avoid redundant work.
Incremental edge addition: only add edges with weight strictly less than the current limit.
Time complexity: O(E log E + Q log Q) for sorting plus near O(E + Q) for DSU operations.
Alternative approaches: binary search on MST or Kruskal reconstruction tree, and their trade-offs.
Edge cases: queries with limit smaller than all edge weights, nodes already connected, self-loops, and multiple edges.

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