Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Uber SWE interview with a graph-based division problem. The question looked like a math puzzle at first but it's really a graph traversal under the hood.

Questions Asked (1)

You're given a list of equations like A/B = k (where k is a real number) and a list of queries asking you to compute C/D. Return the result for each query, or -1.0 if it can't be determined.

Algorithms & Data Structures

Author's notes

Took me an embarrassingly long time to see this as a graph problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the equations as a directed graph where each variable is a node and each equation A/B = k creates two directed edges: A→B with weight k and B→A with weight 1/k. For each query C/D, perform a graph traversal (DFS or BFS) from C to D, multiplying edge weights along the path; if no path exists, return -1.0.

Pro tip: Precompute connected components and cache results for frequently queried pairs to avoid redundant traversals, and always handle edge cases like C == D (return 1.0) and division by zero (though k is real, ensure no zero weights).

1. Build the graph

Create an adjacency list where each node maps to a list of (neighbor, weight) pairs. For each equation A/B = k, add edge A→B with weight k and B→A with weight 1/k.

2. Handle trivial queries

If C == D, return 1.0 immediately. If either C or D is not in the graph, return -1.0.

3. Traverse for each query

For each query C/D, perform DFS or BFS from C to D, multiplying edge weights along the path. If D is reached, return the product; otherwise, return -1.0.

4. Optimize with caching

Optionally, cache results for repeated queries or precompute all-pairs reachability within each connected component to speed up multiple queries.

Key Points to Mention

Graph representation: nodes as variables, edges as division relationships with weights.
Bidirectional edges: A/B = k implies B/A = 1/k.
Path product: the value of C/D is the product of edge weights along the path from C to D.
DFS/BFS traversal to find a path and compute the product.
Handling disconnected components: return -1.0 if no path exists.
Edge cases: C == D returns 1.0; variables not in any equation return -1.0.

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