Jane Street Software Engineer Onsite Coding Questions

## Problem Given a matrix of exchange rates between `n` currencies, detect whether an arbitrage opportunity exists — i.e., a cycle of exchanges starting and ending at the same currency that results in a profit. ```python def has_arbitrage(rates: list[list[float]]) -> bool: pass def find_arbitrage_cycle(rates: list[list[float]]) -> list[int] | None: # Return the sequence of currency indices forming the cycle, or None pass ``` ## Example ``` rates = [ # USD EUR GBP [1.0, 0.9, 0.75], # from USD [1.12, 1.0, 0.83], # from EUR [1.35, 1.22, 1.0 ], # from GBP ] # USD -> EUR -> GBP -> USD: # 1.0 * 0.9 * 0.83 * 1.35 = 1.008 > 1.0 -> arbitrage! has_arbitrage(rates) -> True find_arbitrage_cycle(rates) -> [0, 1, 2, 0] # USD->EUR->GBP->USD ``` ## Follow-ups 1. What graph algorithm detects this? Why does taking log of rates convert this to shortest-path? 2. What is the time complexity of your approach for `n` currencies? 3. In practice, bid/ask spreads and transaction fees eat into arbitrage. How do you model them? 4. How would you handle rates that change in real time?

## Problem Implement a three-way merge: given a **base** version and two branches (`ours` and `theirs`), produce a merged result. If both branches changed the same lines differently, mark as a conflict. Changes to non-overlapping lines are merged automatically. ```python def three_way_merge( base: list[str], ours: list[str], theirs: list[str] ) -> list[str]: # Conflict regions marked as: # ["<<<<<<< ours", ...ours lines..., "=======", ...theirs lines..., ">>>>>>> theirs"] pass ``` ## Example ``` base = ["a", "b", "c", "d"] ours = ["a", "X", "c", "d"] # changed line 2: b->X theirs = ["a", "b", "c", "Y"] # changed line 4: d->Y three_way_merge(base, ours, theirs) # -> ["a", "X", "c", "Y"] (no conflict: different lines changed) ours2 = ["a", "X", "c", "d"] theirs2 = ["a", "Z", "c", "d"] # -> ["a", "<<<<<<< ours", "X", "=======", "Z", ">>>>>>> theirs", "c", "d"] ``` ## Follow-ups 1. What diff algorithm do you use as the foundation (LCS, Myers diff)? 2. How do you handle moves (a block deleted in one place and inserted elsewhere)? 3. How does this extend to structured formats like JSON or XML where line-level diffs lose semantics?

## Problem Implement a fixed-size circular ring buffer with enqueue, dequeue, and overflow handling. ## Likely LeetCode equivalent Similar to Design Circular Queue (LC 622). ## Tags queue, design, jane_street