Compute maximum currency exchange rate
Company: Two Sigma
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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`.
Quick Answer: This question evaluates understanding of graph algorithms and multiplicative path optimization by modeling currency exchanges as a directed weighted graph where exchange rates compose multiplicatively.