Katkat
Back

Detect Currency Arbitrage and Return a Profitable Conversion Cycle

Citadel SecuritiesSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Given a list of currency conversion rates, determine whether an arbitrage opportunity exists and return a sequence of conversions that ends in the starting currency with more money than it began with. Tests graph modeling, cycle detection, reconstruction of the profitable sequence, and handling of floating-point precision.

You are given a list of currency conversion quotes. A quote (from, to, rate) means that one unit of currency from can be converted into rate units of currency to. An arbitrage opportunity is a sequence of conversions that starts and ends in the same currency and finishes with more money than it started with.

Assume the quotes arrive as a list of (from, to, rate) tuples with currency codes as strings, for example ("USD", "EUR", 0.9). Determine whether an arbitrage opportunity exists and, if it does, return a sequence of conversions that makes money, written as the list of currencies visited, such as ["USD", "EUR", "GBP", "USD"].

Clarifying Questions

  • If only USD -> EUR is quoted, can you also convert EUR -> USD at the reciprocal rate, or only in the listed directions?
  • Are there fees or bid/ask spreads, or does every conversion happen exactly at the quoted rate and for any amount?
  • Rates are floating-point numbers. Does any product of rates above one count as making money, or only a gain above some tolerance?
  • If several profitable sequences exist, should you return any one of them, the shortest, or the most profitable?
  • Can the same pair be quoted more than once with different rates?
  • Roughly how many currencies and quotes must the solution handle?

Part 1 — Does an opportunity exist?

Decide whether at least one profitable sequence of conversions exists.

What This Part Should Cover

  • A graph model of the quotes and the condition a profitable cycle satisfies in that model.
  • An algorithm that detects such a cycle anywhere in the graph, not only among currencies reachable from one chosen start, with its time complexity.
  • A tolerance rule, so floating-point rounding neither creates nor hides opportunities.

Part 2 — Return a profitable sequence

When an opportunity exists, return one concrete sequence of conversions that makes money, in conversion order, starting and ending at the same currency.

What This Part Should Cover

  • Bookkeeping during detection that makes the cycle recoverable.
  • A reconstruction that returns a genuine cycle, in the forward direction, with no leading path into it.
  • A final check that the returned sequence really multiplies to more than one.

Hints

Hint 1

Products into sums: The gain of a sequence is the product of its rates, while standard graph algorithms add edge weights. Look for a monotone transformation of each rate that turns "the product exceeds one" into a statement about a sum.

Hint 2

Keep a trail: Record enough during detection to walk backward from where the problem showed up. Check whether the vertex where you notice it is guaranteed to lie on the cycle itself.

Follow-up questions

  • How would you find the most profitable cycle rather than any profitable one, and why is that much harder?
  • How would you account for bid/ask spreads and per-conversion fees?
  • If quotes change continuously, how would you re-check for opportunities after each update without starting from scratch?
  • In a real trading system, why might a detected opportunity no longer be profitable by the time you trade it?