Spot a triangular arbitrage in FX rates
Asked at Jump Trading, Jane Street
You have a matrix of exchange rates: rates[i][j] is how many units of currency j you get for one unit of i (0 means no direct market). Arbitrage exists if some cycle of conversions returns more than you started with, the product of rates around the cycle exceeds 1. Detect whether any arbitrage exists.
rates = [[1, 2.0, 1],
[0.6, 1, 1],
[1, 1, 1]]
-> True # A->B->A gives 2.0 * 0.6 = 1.2 > 1
Return whether an arbitrage cycle exists.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.