Currency Conversion: Build a Conversion Graph and Find Exchange Rates Between Any Two Currencies

Question

## Problem

You are given a list of direct exchange rates between currency pairs. Given a source currency and a target currency, find the effective exchange rate through any chain of conversions, or return -1.0 if no path exists.

```python
from typing import List

def find_exchange_rate(
    rates: List[List],
    queries: List[List[str]]
) -> List[float]:
    # rates: [["USD","EUR", 0.92], ["EUR","GBP", 0.86], ...]
    # queries: [["USD","GBP"], ...]
    # return: effective rate for each query, or -1.0
    pass
```

**Example:**
```
rates = [["USD","EUR",0.92],["EUR","GBP",0.86]]
queries = [["USD","GBP"],["GBP","USD"],["USD","JPY"]]

USD->GBP: 0.92 * 0.86 = 0.7912
GBP->USD: 1/(0.92*0.86) = 1.264
USD->JPY: no path -> -1.0

Output: [0.7912, 1.264, -1.0]
```

## Approach

Model as a weighted directed graph (add both directions: A->B with rate r, B->A with rate 1/r). BFS/DFS with multiplicative path cost, or Floyd-Warshall for all pairs.

## Follow-ups

1. How do you detect an arbitrage opportunity (a cycle whose product > 1.0)?
2. How would you handle rate updates in real time without recomputing the full graph?
3. What numerical precision issues arise when chaining many floating-point multiplications?
4. How would you find the path with maximum rate (best exchange route) vs. any valid path?

Currency Conversion: Build a Conversion Graph and Find Exchange Rates Between Any Two Currencies

Question Details

Full Details

Topics

More from Stripe