Currency Exchange Rate Between Two Currencies via Chained Conversions
Company: Mercor
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a table of currency exchange rates. Each entry `[from, to, rate]` means that 1 unit of currency `from` is worth `rate` units of currency `to`. For example, `["USD", "GBP", 0.77]` means that 1 USD equals 0.77 GBP.
Given a source currency and a target currency, return the exchange rate from source to target: how many units of `target` 1 unit of `source` is worth. The table may not list the pair directly, so a conversion can pass through one or more intermediate currencies.
In the interview this was an algorithm round without code, so be ready to explain your approach and its time and space complexity.
### Function Signature
```python
def exchange_rate(rates: list[tuple[str, str, float]], source: str, target: str) -> float:
```
### Rules
- Each entry is a triple `(from, to, rate)`; the examples write entries as lists.
- Every entry can be used in both directions: `[A, B, r]` also means that 1 `B` equals `1 / r` units of `A`.
- Converting through intermediate currencies multiplies the rates along the way: if 1 `A` equals `x` units of `B` and 1 `B` equals `y` units of `C`, then 1 `A` equals `x * y` units of `C`.
- The table is consistent: every chain of conversions between the same two currencies gives the same rate, apart from floating-point rounding. The exact answer is therefore unique.
- If `source == target`, return `1.0`, even when that currency does not appear in the table.
- Otherwise, if no chain of entries connects `source` to `target`, including when either currency does not appear in the table, return `-1.0`.
- A positive answer is accepted when its relative error from the exact rate is at most `1e-6`. `-1.0` must be returned exactly when no conversion exists.
### Constraints
- `0 <= len(rates) <= 10000`
- Every currency code, including `source` and `target`, is a string of 3 uppercase English letters.
- In every entry `from != to`, and each unordered pair of currencies appears in at most one entry.
- `1e-3 <= rate <= 1e3` for every entry.
- The exact rate between any two connected currencies lies between `1e-9` and `1e9`, so no intermediate product overflows or underflows a 64-bit float.
### Examples
**Example 1**
```text
Input: rates = [["USD", "GBP", 0.77], ["GBP", "EUR", 1.2]], source = "USD", target = "EUR"
Output: 0.924
```
1 USD equals 0.77 GBP and 1 GBP equals 1.2 EUR, so 1 USD equals 0.77 * 1.2 = 0.924 EUR. A floating-point result that differs from 0.924 only in the last digits is accepted.
**Example 2**
```text
Input: rates = [["USD", "GBP", 0.77], ["GBP", "EUR", 1.2]], source = "EUR", target = "USD"
Output: 1.082251
```
The chain runs backward, so each rate is inverted: 1 EUR equals 1 / 1.2 GBP, and 1 GBP equals 1 / 0.77 USD. The exact rate is 1 / 0.924 = 250 / 231, shown here rounded to six decimal places.
**Example 3**
```text
Input: rates = [["USD", "GBP", 0.77], ["JPY", "KRW", 9.5]], source = "USD", target = "KRW"
Output: -1.0
```
USD and GBP are connected only to each other, and JPY and KRW only to each other, so no chain of entries reaches KRW from USD.
Overview: Given a list of pairwise currency exchange rates such as USD to GBP at 0.77, compute the rate from a source currency to a target currency, converting through intermediate currencies and using rates in reverse where needed. It tests reasoning about chained conversions, unknown or unreachable currencies, and a clear time and space complexity analysis.