Currency Arbitrage Graph Detection | Dataford Interview Questions

Write a program to detect currency exchange arbitrage opportunities across multiple trading pairs using graph algorithms.

Represent each currency as a graph vertex and each directed exchange rate as an edge. Implement detect_arbitrage(rates), where rates is a dictionary mapping a currency to dictionaries of directly tradable currencies and rates. Return one arbitrage cycle as a list of currency codes whose first and last elements are equal, or return [] when no profitable cycle exists. An arbitrage cycle has a product of exchange rates greater than 1.

Example: {"USD": {"EUR": 0.9}, "EUR": {"USD": 1.2}} returns ["USD", "EUR", "USD"]. A three-currency cycle is also valid.

Constraints: currencies are uppercase strings, rates are positive floats, and at most 200 currencies and 2,000 trading pairs are provided.

Constraints

1 <= number of currencies <= 200
1 <= number of directed trading pairs <= 2000
Currency codes are non-empty uppercase strings
Every exchange rate is a positive float
The returned cycle must begin and end with the same currency

Function Signature

def detect_arbitrage(rates):

Your question is Currency Arbitrage Graph Detection. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem