How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Uber during technical interviews.

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.

Input: ([['USD','CAD'],['CAD','EUR']], [2.0, 1.5], 'EUR', 'USD')

Expected Output: -1.0

Explanation: Edges are directed; there is no path from EUR back to USD, so return -1.0.

Input: ([['USD','CAD']], [2.0], 'USD', 'JPY')

Expected Output: -1.0

Explanation: JPY does not appear as a reachable node, so no path exists.

Input: ([], [], 'USD', 'CAD')

Expected Output: -1.0

Explanation: Empty graph: no edges, so src and dst are unconnected.

Input: ([['A','B'],['B','C'],['C','D']], [2.0, 3.0, 0.5], 'A', 'D')

Expected Output: 3.0

Explanation: A->B->C->D: 2.0 * 3.0 * 0.5 = 3.0.

Input: ([['A','B']], [5.0], 'A', 'A')

Expected Output: 1.0

Explanation: Source equals destination, so the conversion ratio is 1.0 by definition.

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.

Input: ([['A','B'],['B','A'],['A','C']], [10.0, 0.05, 2.0], 'A', 'C')

Expected Output: 2.0

Explanation: A->C = 2.0. The A->B->A loop is blocked by the simple-path rule, so it cannot revisit A; best is 2.0.

Input: ([['A','B'],['B','C'],['A','C']], [2.0, 5.0, 3.0], 'A', 'C')

Expected Output: 10.0

Explanation: Direct A->C = 3.0; A->B->C = 2.0 * 5.0 = 10.0. Maximum is 10.0.

Input: ([['USD','CAD']], [2.0], 'USD', 'JPY')

Expected Output: -1.0

Explanation: JPY is unreachable, so return -1.0.

Input: ([], [], 'X', 'Y')

Expected Output: -1.0

Explanation: Empty graph: no path from X to Y.

Input: ([['A','B']], [7.0], 'A', 'A')

Expected Output: 1.0

Explanation: Source equals destination, ratio is 1.0.

Input: ([['A','B'],['B','C'],['C','D'],['A','D']], [2.0, 2.0, 2.0, 3.0], 'A', 'D')

Expected Output: 8.0

Explanation: Direct A->D = 3.0; A->B->C->D = 2.0 * 2.0 * 2.0 = 8.0. Maximum is 8.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).

Quick Overview

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.