Detect Currency Arbitrage and Return a Profitable Conversion Cycle

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. ```hint 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. ``` #### 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. ```hint 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. ``` #### 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. ### What a Strong Answer Covers - A correctness argument that links profitable conversion sequences to the property the algorithm detects. - Time and space complexity in terms of the number of currencies and quotes, and when a different algorithm suits dense quotes better. - Numerical robustness: why the transformation helps and how the tolerance is chosen. - Tests: no opportunity, a two-currency loop, a currency quoted against itself, disconnected groups of currencies, and reciprocal quotes whose product is exactly one. ### 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?