Detect Currency Arbitrage After a Cycle Fee
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Detect Currency Arbitrage After a Cycle Fee
You are given a matrix of positive currency exchange rates, where rates[i][j] units of currency j are received for one unit of currency i. Determine whether any exchange sequence of between 1 and n steps starts and ends at the same currency and multiplies the starting amount by more than 1.0001. The threshold represents a fee equal to 0.01 percent of the starting amount charged once for the completed sequence.
## Function Contract
Implement `has_arbitrage(rates) -> bool`.
## Constraints
- 1 <= number of currencies n <= 50.
- The matrix is square and every rate is a positive finite number.
- Currencies may repeat, but the candidate sequence contains at most n exchanges.
- Comparisons should tolerate only ordinary floating-point roundoff, not erase the stated 1.0001 threshold.
## Examples
```text
rates = [[1.0, 0.5], [2.0, 1.0]]
output = false
```
```text
rates = [[1.0, 2.0], [0.51, 1.0]]
output = true
```
```hint Transform products
Taking logarithms converts multiplication along an exchange sequence into addition.
```
```hint Bound the path state
For each start currency and step count, track the best log-value that reaches every current currency.
```
Overview: You are given a matrix of positive currency exchange rates, where rates[i][j] units of currency j are received for one unit of currency i. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given positive finite exchange rates, return whether any sequence of one through `n` exchanges starts and ends at the same currency and multiplies the starting amount by strictly more than `1.0001`. Currencies may repeat; the threshold applies once to the completed sequence.
Constraints
- 1 <= n <= 50 and rates is an n by n matrix of positive finite numbers.
- A candidate sequence uses between one and n exchanges and may repeat currencies.
- Profit requires a completed cycle product strictly greater than 1.0001.
- Floating-point handling may tolerate ordinary roundoff but must preserve the stated threshold.
Examples
Input: ([[1.0]],)
Expected Output: False
Explanation: A one-currency identity exchange does not beat the fee threshold.
Input: ([[1.0001]],)
Expected Output: False
Explanation: A cycle equal to the stated threshold is not strictly profitable.
Hints
- Test one currency, a cycle exactly at the fee threshold, and one just above it.
- Include a profitable multi-currency cycle and a consistent-rate matrix whose cycles all multiply to one.
- Use a favorable path that does not return to its starting currency to confirm it does not qualify.