Detect currency arbitrage with costs
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Overview: This question evaluates a candidate's competency in algorithmic problem modeling, graph-based cycle detection, and numerical reasoning about exchange rates and transaction costs.
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.