Currency Exchange Rate Between Two Currencies via Chained Conversions

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

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

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

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

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.