How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Optiver.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Optiver during technical interviews.

Detect currency arbitrage with costs | Optiver Coding Question

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.

Input: ([[1.0, 0.5, 2.0], [2.0, 1.0, 4.0], [0.5, 0.25, 1.0]],)

Expected Output: False

Explanation: All cycles multiply to exactly 1.0, so after the 0.01% cost every cycle loses money.

Input: ([[1.0, 1.00005], [1.0, 1.0]],)

Expected Output: False

Explanation: The best 2-currency cycle has product 1.00005, which is less than the required 1.0001.

Input: ([[1.0, 1.0001], [1.0, 1.0]],)

Expected Output: False

Explanation: The cycle product is exactly 1.0001, so after subtracting the cost the final amount equals the initial amount, not strictly higher.

Input: ([[1.0, 0.9, 1.1], [1.2, 1.0, 0.95], [0.8, 1.05, 1.0]],)

Expected Output: True

Explanation: Cycle 0 -> 1 -> 0 has product 0.9 * 1.2 = 1.08, which is greater than 1.0001.

Input: ([[1.0, 1.1, 0.8], [0.9, 1.0, 1.1], [1.1, 0.9, 1.0]],)

Expected Output: True

Explanation: No 2-currency cycle is profitable, but cycle 0 -> 1 -> 2 -> 0 has product 1.1 * 1.1 * 1.1 = 1.331.

Solution

def solution(R):
    import math

    n = len(R)
    if n < 2:
        return False

    # A cycle is profitable after cost iff product_of_rates > 1.0001.
    threshold_log = math.log1p(0.0001)
    eps = 1e-12

    logR = [[math.log(R[i][j]) for j in range(n)] for i in range(n)]
    full_mask = 1 << n
    neg_inf = float('-inf')

    # For each possible start currency, use subset DP to find the best
    # log-product path from start to every last currency without repeats.
    for start in range(n):
        dp = [[neg_inf] * n for _ in range(full_mask)]
        dp[1 << start][start] = 0.0

        for mask in range(full_mask):
            if (mask & (1 << start)) == 0:
                continue

            for last in range(n):
                current = dp[mask][last]
                if current == neg_inf:
                    continue

                # Close the cycle by returning to start. Ignore the zero-length
                # path where last == start.
                if last != start and current + logR[last][start] > threshold_log + eps:
                    return True

                # Extend to an unvisited currency.
                remaining = (full_mask - 1) ^ mask
                while remaining:
                    bit = remaining & -remaining
                    nxt = bit.bit_length() - 1
                    new_mask = mask | bit
                    new_value = current + logR[last][nxt]
                    if new_value > dp[new_mask][nxt]:
                        dp[new_mask][nxt] = new_value
                    remaining -= bit

    return False

Time complexity: O(K^3 * 2^K). Space complexity: O(K * 2^K + K^2).

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.

Quick 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.