Detect currency arbitrage with costs
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Quick Answer: 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 x K matrix R of currency exchange rates. R[i][j] is the amount of currency j obtainable for one unit of currency i, and R[i][i] = 1.0. A valid exchange cycle starts at a currency, visits one or more other currencies without repeating any currency, and returns to the starting currency. If the product of the exchange rates along the cycle is P, then starting with amount A yields A * P before costs. Each completed cycle has a transaction cost equal to 0.01% of the initial amount A, so the final amount is A * P - 0.0001 * A. Return True if there exists any cycle whose final amount is strictly greater than the initial amount; otherwise return False.
Constraints
- 0 <= K <= 12
- R is a K x K matrix
- R[i][j] > 0 for all valid i, j
- R[i][i] = 1.0 for all valid i
- A valid cycle must use at least 2 exchanges and may not repeat a currency except for returning to the start
- Apart from exact boundary cases, test data will not depend on floating-point differences smaller than 1e-12
Examples
Input: ([],)
Expected Output: False
Explanation: With no currencies, no exchange cycle exists.
Input: ([[1.0]],)
Expected Output: False
Explanation: A single currency has only R[0][0] = 1.0, which is not a profitable exchange cycle.
Hints
- If a cycle has exchange-rate product P, the cost condition simplifies to P > 1.0001.
- Products along paths can be converted to sums by taking logarithms. Consider dynamic programming over subsets to avoid repeating currencies in a cycle.