Compute currency conversion via graph search
Company: Uber
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a list of currency pairs, e.g., [('USD','CAD'), ('CAD','EUR'), ...], and a parallel list of conversion ratios [1.1, 1.2, ...] where ratio r means 1 unit of the first currency converts to r units of the second, implement a function rate(src, dst) that returns the conversion ratio from src to dst, or -1 if no path exists. Specify your data structures, the search algorithm (e.g., build a directed graph and use DFS/BFS to find a path while multiplying edge weights), and analyze time and space complexity. Follow-up: if conversions are directional and not reciprocal, compute the best achievable rate from src to dst. Explain how to model this as a weighted directed graph and select an appropriate shortest-path algorithm (e.g., transform multiplicative weights with -log and use Dijkstra), and discuss handling cycles/arbitrage and floating-point precision.
Quick Answer: This question evaluates graph modeling and pathfinding with weighted edges, numerical reasoning about multiplicative rates and floating-point precision, and the ability to analyze algorithmic time and space complexity.
Currency Conversion via Graph Search
You are given a list of directed currency `pairs`, e.g. `[('USD','CAD'), ('CAD','EUR')]`, and a parallel list of conversion `ratios`, e.g. `[1.1, 1.2]`, where a ratio `r` for pair `(a, b)` means 1 unit of `a` converts to `r` units of `b`.
Implement `solution(pairs, ratios, src, dst)` that returns the conversion ratio from `src` to `dst` following the directed edges, or `-1.0` if no path exists. If `src == dst` the answer is `1.0`.
Model the input as a directed graph (adjacency list mapping each currency to a list of `(neighbor, ratio)` edges) and run a BFS/DFS from `src`, multiplying edge weights along the path. Because conversions here are consistent, any `src -> dst` path yields the same product, so the first path found is a valid answer.
Return the product of ratios along a path from `src` to `dst`, or `-1.0` if unreachable.
Constraints
- 0 <= number of pairs == len(ratios) <= 10^4
- Each ratio is a positive real number (ratio > 0).
- Currency codes are short non-empty strings.
- Edges are directed: a pair (a, b) does NOT imply an edge b -> a.
- If src == dst, return 1.0 even if the currency never appears in any pair.
Examples
Input: ([['USD','CAD'],['CAD','EUR']], [2.0, 1.5], 'USD', 'EUR')
Expected Output: 3.0
Explanation: USD->CAD (2.0) then CAD->EUR (1.5): 2.0 * 1.5 = 3.0.
Input: ([['USD','CAD'],['CAD','EUR']], [2.0, 1.5], 'USD', 'CAD')
Expected Output: 2.0
Explanation: Single direct edge USD->CAD with ratio 2.0.
Hints
- Build an adjacency list: map each currency to a list of (neighbor, ratio) edges.
- Run BFS or DFS from src, carrying the running product of ratios; stop when you reach dst.
- Use a visited set to avoid cycles. In a consistent graph every src->dst path gives the same product, so the first one found is correct.
- Handle the src == dst case (return 1.0) and the unreachable case (return -1.0) explicitly.
Best Achievable Currency Rate (Non-Reciprocal Conversions)
Follow-up: now conversions are genuinely directional and NOT reciprocal — the rate from A to B and the rate from B to A are independent, and there may be multiple routes between two currencies with different overall products. Among all paths from `src` to `dst`, return the BEST (maximum) achievable conversion ratio.
Implement `solution(pairs, ratios, src, dst)` that returns the maximum product of edge ratios over any simple path from `src` to `dst`, or `-1.0` if no path exists. If `src == dst`, return `1.0`.
Model the input as a weighted directed graph. To maximize a product of positive weights you can equivalently minimize the sum of `-log(weight)` and run a shortest-path algorithm (e.g. Dijkstra when all `-log` weights are non-negative, i.e. all ratios <= 1; Bellman-Ford for the general case, which also detects positive-product cycles / arbitrage). The reference implementation explores all simple paths (no node repeated) with DFS, which directly handles arbitrary ratios and naturally avoids infinite loops from cycles. Floating-point products should be compared with care in production; tests here use exactly representable values.
Constraints
- 0 <= number of pairs == len(ratios) <= number of edges in the graph.
- Each ratio is a positive real number; a->b and b->a may have unrelated ratios.
- Paths considered are simple (no repeated node), so cycles cannot inflate the product unboundedly.
- Return the maximum product over all simple src->dst paths, or -1.0 if dst is unreachable.
- If src == dst, return 1.0.
Examples
Input: ([['USD','CAD'],['CAD','USD']], [2.0, 0.4], 'USD', 'CAD')
Expected Output: 2.0
Explanation: Edges are non-reciprocal (USD->CAD is 2.0, CAD->USD is 0.4). Only the direct USD->CAD path reaches CAD, giving 2.0.
Input: ([['A','B'],['A','C'],['C','B']], [2.0, 4.0, 3.0], 'A', 'B')
Expected Output: 12.0
Explanation: Direct A->B = 2.0; detour A->C->B = 4.0 * 3.0 = 12.0. The maximum is 12.0.
Hints
- Maximizing a product of positive weights is equivalent to minimizing the sum of -log(weight); a shortest-path framing falls out naturally.
- If every ratio is <= 1 the -log weights are non-negative and Dijkstra works; otherwise some weights are negative and you need Bellman-Ford (which also detects arbitrage cycles).
- A direct approach: DFS every simple path (track a visited set, multiply ratios, keep the running maximum at dst), backtracking by removing nodes from visited.
- Restricting to simple paths is what makes the search terminate; a positive-product cycle would otherwise let the product grow without bound (arbitrage).