Convert amounts between multiple currencies
Company: Rippling
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a set of direct currency exchange rates and a list of queries. Each exchange rate gives you how to convert from one currency to another.
- You can assume there are up to \(10^4\) distinct currencies.
- You are given `n` direct exchange rates, each described as: `from_currency`, `to_currency`, `rate`, meaning:
- 1 unit of `from_currency` can be exchanged for `rate` units of `to_currency`.
- Exchange rates are **directed**: if you know `A -> B` at rate `r`, you **cannot** assume you know `B -> A` unless an explicit rate is given.
- You can chain exchanges: if you know `A -> B` and `B -> C`, then you can exchange from `A` to `C` via `B`.
- You may assume that if a chain exists, the effective rate is the product of rates along the path.
You are also given `q` queries. Each query is of the form:
- `source_currency`, `target_currency`, `amount`.
For each query, compute the **maximum** amount of `target_currency` you can obtain by converting the given `amount` units of `source_currency`, using zero or more intermediate currencies and the available direct exchange rates.
- If no conversion path exists from `source_currency` to `target_currency`, return `-1` for that query.
- You may assume there are no arbitrage cycles that increase money unboundedly (i.e., no cycles whose product of rates is greater than 1).
**Input format (conceptual):**
- Integer `n` — number of direct exchange rates.
- Next `n` lines: `from_currency to_currency rate` (e.g., `USD EUR 0.9`).
- Integer `q` — number of queries.
- Next `q` lines: `source_currency target_currency amount`.
**Output:**
- For each query, output a real number representing the maximum amount of `target_currency` you can obtain, or `-1` if it is impossible.
**Task:**
Describe an efficient algorithm to answer all queries.
- Clearly specify the data structures you will use.
- State the time and space complexity in terms of `n` and `q`.
Quick Answer: This question evaluates understanding of graph modeling and path-optimization in directed weighted graphs, specifically reasoning about chained conversions and maximizing multiplicative path weights.
You are given directed currency exchange rates and a list of conversion queries. Each rate `(from_currency, to_currency, rate)` means 1 unit of `from_currency` can be exchanged for `rate` units of `to_currency`. You may chain multiple exchanges, and the effective rate of a path is the product of its edge rates. For each query `(source_currency, target_currency, amount)`, return the maximum amount of `target_currency` obtainable from the given `amount` of `source_currency`. If no conversion path exists, return `-1`. A zero-length conversion is allowed, so converting a currency to itself returns the original amount. You may assume there is no arbitrage cycle whose product is greater than 1.
Constraints
- 0 <= len(rates) <= 2 * 10^4
- 0 <= len(queries) <= 10^4
- There are at most 10^4 distinct currencies in the rate list
- All exchange rates are positive
- No directed cycle has a product of rates greater than 1
Examples
Input: ([('USD', 'EUR', 0.9), ('EUR', 'JPY', 130.0), ('USD', 'JPY', 100.0)], [('USD', 'JPY', 2.0), ('JPY', 'USD', 1.0), ('USD', 'USD', 5.0)])
Expected Output: [234.0, -1, 5.0]
Explanation: For USD -> JPY, the best path is USD -> EUR -> JPY with rate 0.9 * 130 = 117, so 2 * 117 = 234. There is no path from JPY to USD. Converting USD to itself uses zero exchanges, so the answer is 5.0.
Input: ([('A', 'B', 2.0), ('A', 'B', 3.0), ('B', 'C', 4.0), ('A', 'C', 10.0)], [('A', 'C', 1.0), ('C', 'C', 2.0)])
Expected Output: [12.0, 2.0]
Explanation: Between the duplicate A -> B edges, the better rate is 3.0. Then A -> B -> C gives 3 * 4 = 12, which beats the direct rate 10.0. Converting C to C returns the original amount.
Hints
- A product along a path becomes a sum if you take logarithms. Maximizing a product can be turned into minimizing a path cost.
- After transforming each edge weight to `-log(rate)`, the graph has no negative cycles. Reweight once, then run Dijkstra for each distinct query source.