It was a low-level-design problem.
Core problem: An Exchange Arbitrage System for stocks.
Assume there are multiple exchanges, each with a market feed continuously publishing bid and ask prices for different instruments or stocks. Design and implement an arbitrage strategy. The example gave AAPL on exchange A a bid of $1.00 and an ask of $1.10, while exchange B had a bid of $0.90 and an ask of $1.00. It described buying AAPL on B at $1.00 and simultaneously selling it on A at $1.00, or taking orders within that spread. The example described this as risk-free arbitrage profit, such as $0.10 per share.
Guiding question: How should exchanges and instruments be abstracted?
Quote / OrderBook Entry: Contains InstrumentID, ExchangeID, BidPrice, BidSize, AskPrice, AskSize, and Timestamp. An Instrument has a globally unique identifier, such as a Symbol or TickerID.
Exchange: Maintains its local OrderBook Snapshot and exposes an Order Execution API.
MarketDataListener: Subscribes to and receives feeds from the exchanges.
OrderBookManager: Maintains a global in-memory quote table, providing a fast mapping from (Instrument, Exchange) to the current Best Bid / Best Ask.
ArbitrageEngine: Listens for price changes and checks whether Max(Bid) and Min(Ask) show a price inversion across exchanges, meaning Best Bid is greater than Best Ask.
ExecutionRouter: When an arbitrage opportunity, or edge, is found, sends buy and sell orders to the corresponding exchanges in parallel.
Follow-up: With one million quote updates per second, how would the system maintain high performance and low latency? The interviewer cared a lot about architecture choices and data-structure optimization under high concurrency and low latency. The answer focused on the following areas:
Avoid dynamic memory allocation: Preallocate fixed-size contiguous memory, using arrays, to avoid garbage collection or object creation on the main quote-update path.
Use flat data structures: Store each exchange's current best bid and ask in a two-dimensional array or flat hash table. For example, use (Instrument_ID * Max_Exchanges + Exchange_ID) for direct O(1) addressing into contiguous memory, aiming to greatly improve the CPU cache hit rate.
Incremental updates and local extrema: The proposed approach avoided comparing everything. For each instrument, maintain only a Global Best Bid and a Global Best Ask. When a new quote arrives, trigger arbitrage detection only if its price improves on the current global best bid or ask, avoiding a scan of every exchange for each of the one million updates.
After writing the code, it was Q&A.
Discussion
Loading comments…