Compute maximum currency exchange rate
Company: Two Sigma
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Compute maximum currency exchange rate
You are given a set of currencies and the direct exchange rates between some pairs of them. Each direct exchange rate tells you how many units of one currency you can get for 1 unit of another currency.
Formally:
- There are `n` currencies labeled from `0` to `n - 1`.
- You are given `m` directed exchange rates. Each rate is a triple `(u, v, r)` meaning:
- You can directly exchange from currency `u` to currency `v`.
- If you start with `1` unit of currency `u`, you can obtain `r` units of currency `v` in a single exchange.
- You may perform a sequence of exchanges, chaining them together. If you go from `u -> v` with rate `r1` and then `v -> w` with rate `r2`, the resulting effective rate from `u` to `w` along that path is `r1 * r2`.
- You should assume that you do **not** revisit the same currency in a single exchange path (i.e., paths are simple, without repeated nodes), so the maximum rate is always finite.
You are also given two currency labels `A` (start) and `B` (target). You start with `1` unit of currency `A`.
**Task**
Compute the **maximum possible amount of currency `B`** you can obtain from `1` unit of currency `A` by performing zero or more exchanges.
- If `A == B`, you may choose to perform zero exchanges, in which case you can always end with at least `1` unit of `B`, so the minimum answer is `1.0`.
- If it is impossible to reach currency `B` starting from `A` via any sequence of exchanges, return `-1.0`.
**Input format (one possible specification)**
- Integer `n` — number of currencies.
- Integer `m` — number of direct exchange rates.
- Next `m` lines: each contains `u v r`:
- `u` and `v` are integers in `[0, n-1]`.
- `r` is a real number `> 0` representing the direct exchange rate from `u` to `v`.
- Last line: two integers `A B` — the start and target currencies.
**Output format**
- Output a single real number: the maximum amount of currency `B` obtainable from `1` unit of currency `A` using any sequence of allowed exchanges.
- If `B` is unreachable from `A`, output `-1.0`.
**Example**
Suppose:
- `n = 3` (currencies `0`, `1`, `2`)
- `m = 3`
- Exchange rates:
- `0 1 2.0` (1 unit of `0` → 2 units of `1`)
- `1 2 3.0` (1 unit of `1` → 3 units of `2`)
- `0 2 4.0` (1 unit of `0` → 4 units of `2`)
- `A = 0`, `B = 2`.
Possible paths from `0` to `2`:
- Direct: `0 -> 2` with rate `4.0` → get `4.0` units.
- Via `1`: `0 -> 1 -> 2` with rate `2.0 * 3.0 = 6.0` → get `6.0` units.
The answer is `6.0`, the maximum achievable amount of currency `2`.
### Constraints & Assumptions
- Preserve the scope, facts, inputs, and requested outputs from the prompt above.
- If the prompt leaves a detail unspecified, state a reasonable assumption before relying on it.
- Keep the answer interview-ready: concise enough to present, but concrete enough to implement or evaluate.
### Clarifying Questions to Ask
- Clarify input sizes, value ranges, mutability, return format, and tie-breaking.
- State the target time and space complexity before coding.
- Call out edge cases such as empty inputs, duplicates, invalid values, overflow, and boundary sizes.
### What a Strong Answer Covers
- A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
- A correctness argument that explains why the algorithm covers all required cases.
- Time and space complexity, plus at least one alternative approach when relevant.
- Focused tests for normal cases, edge cases, and failure modes.
### Follow-up Questions
- How would the approach change if the input were streaming or too large for memory?
- What invariants would you assert in production code?
- Which tests would catch off-by-one, duplicate, or tie-breaking bugs?
Quick Answer: Compute maximum currency exchange rate evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
You are given `n` currencies labeled `0` to `n - 1` and a list of `m` directed exchange rates. Each rate is a triple `[u, v, r]` meaning 1 unit of currency `u` can be directly exchanged for `r` units of currency `v` (`r > 0`).
You may chain exchanges: going `u -> v` (rate `r1`) then `v -> w` (rate `r2`) yields an effective rate of `r1 * r2`. Exchange paths are **simple** (no currency is revisited), so the maximum achievable rate is always finite.
Given a start currency `A` and target currency `B`, starting with 1 unit of `A`, return the **maximum amount of currency `B`** obtainable using zero or more exchanges.
Rules:
- If `A == B`, you may perform zero exchanges, so the answer is at least `1.0`.
- If `B` is unreachable from `A`, return `-1.0`.
Implement `solution(n, edges, A, B)` where `edges` is a list of `[u, v, r]` triples. Return a float.
Example: `n = 3`, `edges = [[0,1,2.0],[1,2,3.0],[0,2,4.0]]`, `A = 0`, `B = 2`. Direct `0->2` gives `4.0`; via `1`, `0->1->2` gives `2.0 * 3.0 = 6.0`. The answer is `6.0`.
Constraints
- 1 <= n <= number of currencies (small, suitable for path enumeration)
- 0 <= m (number of edges)
- Each edge is [u, v, r] with 0 <= u, v < n and r > 0
- 0 <= A, B < n
- Paths are simple (no currency revisited), so the maximum rate is finite
- Return 1.0 when A == B, -1.0 when B is unreachable from A
Examples
Input: (3, [[0, 1, 2.0], [1, 2, 3.0], [0, 2, 4.0]], 0, 2)
Expected Output: 6.0
Explanation: Direct 0->2 gives 4.0; via 1, 0->1->2 gives 2.0*3.0=6.0. Max is 6.0.
Input: (2, [[0, 1, 5.0]], 0, 1)
Expected Output: 5.0
Explanation: Single direct edge 0->1 with rate 5.0.
Input: (2, [], 0, 1)
Expected Output: -1.0
Explanation: No edges, so B=1 is unreachable from A=0.
Input: (3, [[0, 1, 2.0]], 1, 1)
Expected Output: 1.0
Explanation: A == B, so zero exchanges yields 1.0 unit of B.
Input: (4, [[0, 1, 1.5], [1, 2, 2.0], [0, 2, 2.5], [2, 3, 4.0]], 0, 3)
Expected Output: 12.0
Explanation: 0->1->2->3 = 1.5*2.0*4.0 = 12.0 beats 0->2->3 = 2.5*4.0 = 10.0.
Input: (1, [], 0, 0)
Expected Output: 1.0
Explanation: Single currency, A == B, answer is 1.0 with no exchanges.
Input: (3, [[0, 1, 2.0], [1, 2, 3.0]], 2, 0)
Expected Output: -1.0
Explanation: Edges only go forward; currency 0 is unreachable from currency 2.
Hints
- Model currencies as nodes and exchange rates as directed weighted edges. The effective rate along a path is the PRODUCT of edge rates, not the sum.
- Because paths must be simple (no repeated currency), use DFS with a backtracking visited set to enumerate paths from A to B and track the maximum product reached at B.
- Handle the two special cases explicitly: A == B returns at least 1.0 (zero exchanges), and if B is never reached, return -1.0.
- Multiply rates as you descend (carry the running product into the recursion) and update the best answer whenever you arrive at B.