Problem Overview

You are building a currency exchange system for a global payments platform. The system needs to convert amounts between different currencies using a set of known exchange rates.

Exchange rates are provided as a comma-separated string in the format "FROM:TO:RATE,FROM:TO:RATE,...", where each entry indicates that 1 unit of the FROM currency equals RATE units of the TO currency.

For example: "USD:EUR:0.85,EUR:GBP:0.88,USD:JPY:110"

The problem is divided into four progressive parts:

• Direct Conversion: Look up a direct exchange rate, supporting both forward and reverse lookups

• Single Intermediate: Allow conversion through exactly one intermediate currency

• Optimal Rate: Find the best possible exchange rate when multiple conversion paths exist

• Unlimited Intermediates: Support conversion chains of any length to find a path between currencies

Important Notes

• There are multiple parts to this problem -- ask the interviewer how many parts there are to better manage your time

• Start with the simplest data structure and extend it as parts get more complex

• Write your own test cases and ensure your code compiles and runs correctly

Part 1: Direct Conversion with Reverse Lookup

Implement a CurrencyConverter class that parses the exchange rate string and provides a method getRate(from, to) that returns the exchange rate between two currencies.

• Forward lookup: If the rate from A to B is given directly

• Reverse lookup: If only the rate from B to A is given, calculate A to B as 1 / rate

` rates = "USD:EUR:0.85,EUR:GBP:0.88,USD:JPY:110" converter = CurrencyConverter(rates)

converter.getRate("USD", "EUR") # Returns 0.85 (direct lookup) converter.getRate("EUR", "USD") # Returns 1.176... (reverse: 1/0.85) converter.getRate("USD", "GBP") # Returns None (no direct rate) `

• Parse the input string efficiently

• Store rates in a way that supports O(1) lookup

• Handle reverse conversion by computing the reciprocal

• Return None when no direct rate exists

• How should we handle precision for floating-point calculations?

• Can there be duplicate or conflicting rates in the input?

• Should we handle same-currency conversion (e.g., USD to USD)?

Extend the solution to find a conversion rate when the two currencies can be connected through exactly one intermediate currency.

` rates = "USD:EUR:0.85,EUR:GBP:0.88,USD:JPY:110" converter = CurrencyConverter(rates)

converter.getRate("USD", "GBP")

Returns 0.748 (USD→EUR→GBP = 0.85 × 0.88)

converter.getRate("GBP", "JPY")

Requires 2 intermediates (GBP→EUR→USD→JPY) -- returns None for Part 2

`

• First check for direct conversion (Part 1)

• If not found, search for a single intermediate currency that connects the two

• Multiply the rates along the path: rate(A→B) × rate(B→C)

• Return None if no path exists with at most one intermediate

When multiple conversion paths exist between two currencies, find and return the best (maximum) exchange rate.

Different paths may yield different rates due to market inefficiencies. The user wants the path that gives them the most units of the target currency.

` rates = "USD:EUR:0.85,USD:GBP:0.75,EUR:GBP:0.88,GBP:CAD:1.7,EUR:CAD:1.45" converter = CurrencyConverter(rates)

converter.getRate("USD", "CAD")

Path 1: USD→GBP→CAD = 0.75 × 1.7 = 1.275

Path 2: USD→EUR→CAD = 0.85 × 1.45 = 1.2325

Path 3: USD→EUR→GBP→CAD = 0.85 × 0.88 × 1.7 = 1.2716

Returns 1.275 (best rate via USD→GBP→CAD)

`

Allow conversion through any number of intermediate currencies. Use graph traversal (BFS or DFS) to find if a path exists and compute the best rate.

` rates = "USD:EUR:0.85,EUR:GBP:0.88,GBP:JPY:150,JPY:AUD:0.012" converter = CurrencyConverter(rates)

converter.getRate("USD", "AUD")

USD→EUR→GBP→JPY→AUD = 0.85 × 0.88 × 150 × 0.012 = 1.3464

converter.getRate("AUD", "USD")

Reverse path, returns 1/1.3464 ≈ 0.7427

`

• Implement graph traversal to find paths of any length

• Handle cycles in the currency graph (avoid infinite loops)

• Track visited currencies to prevent revisiting

• Return the best rate among all valid paths

Hint: Data StructureUse a nested dictionary for Part 1, then transition to an adjacency list for Parts 3-4:

`

Part 1-2: Nested dictionary for direct lookups

self.rates = {} # rates["USD"]["EUR"] = 0.85

Part 3-4: Adjacency list with bidirectional edges

self.graph = defaultdict(list)

graph["USD"] = [("EUR", 0.85), ("JPY", 110)]

graph["EUR"] = [("USD", 1/0.85), ("GBP", 0.88)]

` Store both forward and reverse rates as edges in the graph so you can traverse in either direction.

Hint: Single Intermediate (Part 2)To find a single intermediate, iterate through all known currencies and check if you can get a direct rate from from → intermediate and from intermediate → to:

for intermediate in all_currencies: rate1 = self._get_direct_rate(from_curr, intermediate) rate2 = self._get_direct_rate(intermediate, to_curr) if rate1 is not None and rate2 is not None: return rate1 * rate2 Extract _get_direct_rate as a helper that handles both forward and reverse lookups.

Hint: Graph Traversal (Parts 3-4)Model currencies as nodes and rates as weighted edges. Use BFS or DFS with a visited set to explore all paths:

`

BFS: queue stores (current_currency, accumulated_rate, visited_set)

queue = [(from_curr, 1.0, {from_curr})]

while queue: current, rate, visited = queue.pop(0) for neighbor, edge_rate in self.graph[current]: if neighbor == to_curr: best_rate = max(best_rate, rate * edge_rate) elif neighbor not in visited: queue.append((neighbor, rate * edge_rate, visited | {neighbor})) ` The key insight is to track the best rate found, since different paths may yield different rates.

Full Solution (Python)$3bTime complexity: O(V!) in the worst case where V is the number of currencies, but typically much better with cycle detection via the visited set.

Space complexity: O(V + E) for the adjacency list, O(V) for the visited set during traversal.

Note: This solution handles all four parts with the same code. The DFS naturally finds direct rates (Part 1), single intermediate rates (Part 2), optimal rates among all paths (Part 3), and unlimited chains (Part 4).