Detect currency arbitrage with costs
OptiverSoftware Engineer · Technical ScreenLast updated
This question evaluates a candidate's competency in algorithmic problem modeling, graph-based cycle detection, and numerical reasoning about exchange rates and transaction costs.
You are given a K×K matrix R of currency exchange rates where R[i][j] is the amount of currency j obtainable for one unit of currency i, and R[i][i] = 1 for all i. A closed cycle of exchanges incurs a transaction cost of 0.01% of the initial amount (applied once per completed cycle). Determine whether there exists any cycle of exchanges that yields a strictly higher final amount than the initial after accounting for this cost. Return true if such an arbitrage opportunity exists, otherwise return false.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.