Currency Exchange Arbitrage Detection

Approach Tips

**Key Insight:** Arbitrage = a cycle where the product of exchange rates > 1.0. Transform this into a standard graph problem using logarithms. **The Math Trick:** - Arbitrage: rate₁ × rate₂ × ... × rateₖ > 1 - Take -log: -log(rate₁) + -log(rate₂) + ... + -log(rateₖ) < 0 - This is a **negative cycle** in a graph with edge weights = -log(rate) **Algorithm (Bellman-Ford):** 1. Build a directed graph: each exchange rate `(A, B, r)` becomes an edge A→B with weight `-log(r)` 2. Run Bellman-Ford for V-1 iterations (V = number of currencies) 3. Run one more iteration — if any distance still decreases, a negative cycle (arbitrage) exists ```python def has_arbitrage(currencies, rates): n = len(currencies) dist = [0] * n # start all at 0 (trick: detects cycle from any source) for i in range(n): for (u, v, rate) in rates: new_dist = dist[u] + (-math.log(rate)) if new_dist < dist[v]: if i == n - 1: return True # negative cycle = arbitrage dist[v] = new_dist return False ``` **Alternative — DFS approach:** - From each currency, DFS tracking the cumulative product of rates - If you revisit a currency with product > 1.0 → arbitrage found - Simpler to code but O(V!) worst case without pruning **Complexity:** Bellman-Ford: O(V × E) time, O(V) space. **What interviewers look for:** - Can you model this as a graph problem? (Many candidates don't see the connection) - The log transformation insight (turns multiplication into addition) - Understanding why Bellman-Ford's V-th iteration detects negative cycles - Edge cases: self-loops (USD→USD at rate 1.001), disconnected currency components **Follow-up questions:** - Find the actual arbitrage cycle (track predecessors in Bellman-Ford) - What if rates change in real-time? (incremental updates) - How would you handle this in a real trading system? (latency, transaction costs)