Maximum Currency Conversion Rate
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Maximum Currency Conversion Rate
You are given `N` currency exchange rate pairs. Each pair is a triple `(from_currency, to_currency, rate)`, meaning that 1 unit of `from_currency` can be exchanged for `rate` units of `to_currency`. All rates are strictly positive real numbers.
Given a `source` currency and a `target` currency, find the **best (maximum) overall conversion rate** achievable by chaining one or more exchanges from `source` to `target`. Chaining exchanges multiplies their rates: converting through the sequence `A -> B -> C` yields an overall rate of `rate(A->B) * rate(B->C)`.
Rules and assumptions:
- Exchanges are **directional**: a pair `(A, B, r)` lets you convert `A` to `B` at rate `r`, but does **not** by itself allow converting `B` to `A`. A reverse rate is only available if it appears as its own pair in the input.
- A conversion path must **not visit the same currency more than once** (simple paths only), so a path's length is bounded by the number of distinct currencies.
- If the same directed pair `(from_currency, to_currency)` appears multiple times, use the one with the highest rate.
- If `source == target`, the answer is `1.0`.
- If `target` is unreachable from `source`, return `-1.0`.
### Input
- `pairs`: a list of `N` triples `[from_currency, to_currency, rate]`, where currencies are strings (e.g., `"USD"`, `"EUR"`) and `rate` is a positive float.
- `source`: the starting currency (string).
- `target`: the desired currency (string).
### Output
Return a single float: the maximum achievable conversion rate from `source` to `target`, or `-1.0` if no conversion path exists. Answers within `1e-6` relative or absolute tolerance are accepted.
### Example
```
pairs = [["USD", "EUR", 0.9],
["EUR", "GBP", 0.85],
["USD", "GBP", 0.7],
["GBP", "JPY", 190.0]]
source = "USD"
target = "JPY"
```
Output:
```
145.35
```
Explanation: the path `USD -> EUR -> GBP -> JPY` gives `0.9 * 0.85 * 190.0 = 145.35`, which beats the direct-ish alternative `USD -> GBP -> JPY = 0.7 * 190.0 = 133.0`.
### Constraints
- `1 <= N <= 200`
- Number of distinct currencies `<= 14`
- Currency codes are non-empty strings of up to 10 uppercase letters
- `0 < rate <= 10.0`
- The final answer is guaranteed to fit in a standard 64-bit floating-point value (it will not exceed `1e9`)
- `source` and `target` are guaranteed to appear in at least one pair
Quick Answer: This question evaluates proficiency in graph algorithms and numerical reasoning, specifically modeling directed weighted graphs and optimizing multiplicative exchange rates through path selection.
You are given a set of directed currency exchange rates, provided as two parallel arrays (the same shape as LeetCode 399 "Evaluate Division"):
- `equations[i] = [from_currency, to_currency]` is a directed pair of currency codes.
- `values[i]` is the exchange rate for `equations[i]`: 1 unit of `from_currency` buys `values[i]` units of `to_currency`.
Given a `source` and a `target` currency, return the maximum overall conversion rate achievable by chaining one or more exchanges from `source` to `target`. Chaining multiplies the rates: `A -> B -> C` yields `rate(A->B) * rate(B->C)`.
Rules:
- Exchanges are directional: `[A, B]` lets you convert A to B, but not B to A unless a separate pair `[B, A]` is given.
- A path must be simple (it may not visit the same currency twice), so its length is bounded by the number of distinct currencies.
- If the same directed pair `[from, to]` appears more than once, use its highest rate.
- If `source == target`, return `1.0`.
- If `target` is unreachable from `source`, return `-1.0`.
Answers within `1e-6` absolute or relative tolerance are accepted.
Example:
```
equations = [["USD","EUR"], ["EUR","GBP"], ["USD","GBP"], ["GBP","JPY"]]
values = [0.9, 0.85, 0.7, 190.0]
source = "USD"
target = "JPY"
```
Output: `145.35`
The path `USD -> EUR -> GBP -> JPY` gives `0.9 * 0.85 * 190.0 = 145.35`, which beats `USD -> GBP -> JPY = 0.7 * 190.0 = 133.0`.
Constraints
- 1 <= N (number of pairs) <= 200
- Number of distinct currencies <= 14
- Currency codes are non-empty strings of up to 10 uppercase letters
- 0 < rate <= 10.0
- equations and values have the same length; values[i] is the rate for equations[i]
- The final answer will not exceed 1e9
- source and target each appear in at least one pair
Examples
Input: equations = [["USD","EUR"],["EUR","GBP"],["USD","GBP"],["GBP","JPY"]], values = [0.9,0.85,0.7,190.0], source = "USD", target = "JPY"
Expected Output: 145.35
Explanation: USD->EUR->GBP->JPY = 0.9*0.85*190.0 = 145.35 beats the shorter USD->GBP->JPY = 133.0.
Input: equations = [["USD","EUR"]], values = [0.9], source = "USD", target = "USD"
Expected Output: 1.0
Explanation: source == target, so no conversion is needed and the rate is exactly 1.0.
Hints
- Build a directed graph keyed by from_currency; for each destination keep only the highest rate seen (duplicates use the max).
- Because distinct currencies <= 14 and paths must be simple, a DFS that carries the running product and a visited set explores every valid path cheaply.
- Handle source == target up front (answer 1.0); track the best product reaching target and return -1.0 if it is never reached.