Uber·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Apr 2026Remote

Summary

Uber SWE interview with a graph connectivity problem that looks deceptively straightforward until you realize brute force is going to time out badly. The offline union-find angle is what they're actually testing for.

Questions Asked (1)

Given an undirected weighted graph and a list of queries, for each query determine whether a path exists between two nodes using only edges whose weights are strictly less than a given limit. Return a boolean array of answers.

Algorithms & Data Structures

Author's notes

I started thinking about this as a per-query BFS and immediately knew that wasn't going to scale.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Sort the queries by limit and process them in increasing order, incrementally adding edges with weight less than the current limit to a disjoint-set union (DSU) structure. For each query, check if the two nodes are in the same connected component after adding all eligible edges.

Pro tip: Mention that this offline approach reduces the time complexity to O(E log E + Q log Q) and is more efficient than running BFS/DFS for each query. Also, clarify that edges with weight equal to the limit are excluded because the condition is strictly less than.

1. Understand the problem and constraints

Clarify that the graph is undirected and weighted, and that for each query we need to determine if a path exists using only edges with weight < limit. Note that the answer is a boolean array.

2. Choose the right data structure

Use Disjoint Set Union (DSU) to efficiently maintain connected components as edges are added. DSU supports near-constant time union and find operations.

3. Process queries offline

Sort queries by their limit in ascending order. Also sort edges by weight. Iterate through queries, adding all edges with weight < current limit to the DSU before answering the query.

4. Answer each query

For each query, after adding all eligible edges, check if the two nodes belong to the same component using DSU find. Store the boolean result.

5. Return the results

Collect the boolean answers in the original query order (if queries were sorted, map back to original indices) and return the array.

Key Points to Mention

Disjoint Set Union (Union-Find) with path compression and union by rank/size for efficiency.
Offline processing: sorting queries and edges to avoid repeated graph traversals.
Time complexity: O(E log E + Q log Q + (E+Q) α(N)) where α is the inverse Ackermann function.
Space complexity: O(N + E + Q) for DSU, edges, and queries.
Edge case: queries with limit less than or equal to the minimum edge weight will have no edges added, so only nodes themselves are connected.
Strict inequality: edges with weight equal to the limit are not included.

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