How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Rippling.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Rippling during technical interviews.

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.

Input: ([('X', 'Y', 1.5), ('Y', 'Z', 2.0)], [('X', 'Z', 3.0), ('Z', 'X', 1.0), ('Q', 'Q', 7.0), ('Q', 'X', 1.0)])

Expected Output: [9.0, -1, 7.0, -1]

Explanation: X -> Z is possible through Y with total rate 1.5 * 2.0 = 3.0, so 3.0 units become 9.0. There is no path from Z to X. Q -> Q returns 7.0 even though Q is not in the rate list. Q -> X is impossible.

Input: ([('A', 'B', 0.5), ('A', 'C', 2.0), ('C', 'B', 0.4), ('B', 'D', 3.0), ('C', 'D', 0.7)], [('A', 'D', 10.0)])

Expected Output: [24.0]

Explanation: The best path is A -> C -> B -> D with rate 2.0 * 0.4 * 3.0 = 2.4, so 10.0 becomes 24.0. Other paths produce less.

Input: ([], [('USD', 'EUR', 1.0), ('USD', 'USD', 1.0)])

Expected Output: [-1, 1.0]

Explanation: With no exchange rates, converting between different currencies is impossible. A currency can always remain unchanged, so USD -> USD returns 1.0.

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.

Quick Overview

This question evaluates understanding of graph modeling and path-optimization in directed weighted graphs, specifically reasoning about chained conversions and maximizing multiplicative path weights.