Uber·Machine Learning Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026

Summary

Uber ML engineer interview that went deep into graph algorithms, which I was not fully expecting. The currency conversion problem sounds like a coding warmup but they kept pushing on the design and complexity until it turned into a full system design conversation.

Questions Asked (2)

Given a list of currency pairs and their conversion ratios, implement a function that returns the conversion rate between any two currencies, or -1 if no conversion path exists. Walk through your data structure choices and search algorithm, and analyze time and space complexity.

Algorithms & Data StructuresSystem Design

Author's notes

I jumped straight to BFS on a directed graph, multiplying edge weights along the path.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the currency pairs as a directed graph where nodes are currencies and edges are conversion rates, then use BFS to find the shortest conversion path. For each query, compute the product of rates along the path, returning -1 if no path exists. Discuss trade-offs between BFS and DFS, and consider precomputing all-pairs rates for frequent queries.

Pro tip: Mention that in production systems like Uber's, you'd likely precompute and cache conversion rates using Floyd-Warshall for all-pairs shortest paths, or use a union-find structure for connectivity checks, to handle high query volumes efficiently.

1. Clarify requirements and constraints

Ask about the number of currencies, frequency of queries, whether rates change dynamically, and if negative rates or cycles are possible. This informs data structure and algorithm choices.

2. Choose data structure

Represent the graph using an adjacency list (hash map of currency to list of (neighbor, rate)) for efficient traversal. Alternatively, an adjacency matrix for dense graphs or precomputation.

3. Select search algorithm

Use BFS to find the shortest path in terms of number of conversions, which minimizes rounding errors. For each query, run BFS from source to target, multiplying rates along the path.

4. Analyze time and space complexity

For a single query, BFS takes O(V+E) time and O(V) space. If precomputing all-pairs with Floyd-Warshall, it's O(V^3) time and O(V^2) space, but queries become O(1).

5. Discuss optimizations and edge cases

Consider caching results, handling disconnected components, and dealing with floating-point precision. Mention that if rates are updated frequently, incremental algorithms might be needed.

Key Points to Mention

Graph representation: adjacency list vs. adjacency matrix, and why adjacency list is preferred for sparse graphs.
BFS vs. DFS: BFS finds shortest path in unweighted graphs (minimizing number of conversions), which reduces rounding errors.
Time complexity: O(V+E) per query for BFS, O(V^3) for Floyd-Warshall precomputation.
Space complexity: O(V+E) for adjacency list, O(V^2) for matrix.
Handling cycles: BFS naturally avoids infinite loops by tracking visited nodes.
Floating-point precision: multiplying rates can accumulate errors; consider using logarithms or rational numbers.

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

Follow-up: if currency conversions are directional and not necessarily reciprocal, how would you find the best possible conversion rate from a source currency to a destination? How do you model this as a weighted graph problem, and which shortest-path algorithm applies? Also address cycles and floating-point precision.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is where it got interesting and where I partially fell apart.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model currencies as nodes and directional conversion rates as edge weights, then transform the problem into a shortest-path search by taking the negative logarithm of each rate. Use the Bellman-Ford algorithm to find the best conversion path while detecting negative cycles that indicate arbitrage opportunities, and handle floating-point precision with epsilon comparisons and careful accumulation.

Pro tip: Mention that in production, you'd likely cap the number of hops to avoid excessive fragmentation and use a priority queue with early termination for efficiency, but Bellman-Ford is the safe choice when negative cycles are possible.

1. Model as a directed weighted graph

Create a node for each currency and a directed edge from currency A to B with weight = -log(rate(A→B)). This converts multiplicative rate products into additive path costs.

2. Identify the shortest-path problem

The best conversion rate corresponds to the path with the minimum sum of -log(rate) values, which is equivalent to maximizing the product of rates. This is a single-source shortest-path problem on a graph with possibly negative edge weights.

3. Choose Bellman-Ford for negative cycles

Use Bellman-Ford because it handles negative weights and can detect negative cycles. A negative cycle indicates an arbitrage opportunity (a sequence of conversions yielding more than 1 unit of the source currency).

4. Handle cycles and precision

If a negative cycle exists, the best rate is unbounded (arbitrage). Otherwise, the shortest path gives the optimal rate. Use epsilon comparisons for floating-point equality and consider using log-space to avoid underflow/overflow.

5. Discuss trade-offs and optimizations

Mention that Dijkstra's algorithm works if no negative edges (i.e., all rates ≤ 1) but fails otherwise. For large graphs, consider Johnson's algorithm or A* with a heuristic, and note that real-world systems may limit path length.

Key Points to Mention

Directional edges: rate(A→B) may not equal 1/rate(B→A), so the graph is directed.
Log transformation: -log(rate) turns multiplication into addition, enabling shortest-path algorithms.
Bellman-Ford algorithm: handles negative weights and detects negative cycles (arbitrage).
Negative cycle detection: indicates an arbitrage opportunity, making the best rate unbounded.
Floating-point precision: use epsilon for comparisons, avoid direct equality, and consider log-space to mitigate underflow/overflow.
Trade-offs: Dijkstra's algorithm is faster but only valid if all edge weights are non-negative (i.e., rates ≤ 1).

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