Katkat
Back

Implement an in-memory order book API

CitadelSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design an in-memory data structure for an order book using efficient data structures to support order management and price-level aggregation.

Problem Statement

Design a simple in-memory Order Book for a single financial instrument. The Order Book tracks buy and sell orders. Each order has an order_id (string), price (float), quantity (int), and side ('BUY' or 'SELL').

Implement the following API methods:

  1. add_order(order_id, side, price, quantity): Adds a new order to the book.
  2. cancel_order(order_id): Removes an existing order from the book.
  3. get_best_bid(): Returns the price of the highest BUY order.
  4. get_best_ask(): Returns the price of the lowest SELL order.

Constraints

  • order_id is unique.
  • Multiple orders can exist at the same price level.
  • Your implementation should prioritize average-case efficiency for additions and removals.

Example

# Add orders
add_order("1", "BUY", 100.0, 10)
add_order("2", "BUY", 101.0, 5)
add_order("3", "SELL", 105.0, 20)

# Best bid is 101.0, best ask is 105.0
get_best_bid() # Returns 101.0
get_best_ask() # Returns 105.0

# Cancel the best bid
cancel_order("2")
get_best_bid() # Returns 100.0

Edge Cases

  • Canceling an order that does not exist.
  • Requesting best bid/ask when no orders of that side exist (return None).
  • Updating an order's quantity or price.

Hints

Hint 1

Use a hash map to map `order_id` to its order details for O(1) lookups during cancellation.

Hint 2

Use a balanced binary search tree or a sorted map to store price levels for each side to keep the best prices easily accessible.

Hint 3

Consider how to handle multiple orders at the same price point; perhaps a linked list or queue inside each price level node.

Follow-up questions

  • How would you modify this to support matching engine logic, where new BUY orders automatically execute against existing SELL orders at the same or lower price?
  • What are the concurrency implications if multiple threads attempt to update the order book simultaneously?
  • How would you ensure the data structure remains thread-safe while maintaining high performance?