Design a Limit Order Book - Machine Coding Interview

image.png

Limit Order Book

A limit order book is used in stock exchanges to match a buy order with a sell order based on price and time priority

In Stock trading, exchanges like NYSE (New York Stock Exchange) maintains an order book for every security or stock which is traded on their exchange e.g. GOOG, which is a symbol of Google's stock. There are mainly two kinds of orders customers can send, a buy order, and a sell order. When we use Limit Price, which means buy order with a limit price of $50 can be executed if it found a sell order of $50 or an order of lower price says $49, but it can not be executed with a sell order of price $51. Similarly, a sell order can execute for a price, which is either equal to or higher than the limit price. In general, a LIMIT order executes if it found a specified price or better price(lower in the case of a buy, and higher in the case of sell).

Orders are executed on a first come first serve basis, so exchange also maintains a time priority. Now, let's see the flow, an order comes to exchange, exchange looks order book for that symbol, if it found a match it executes order otherwise, it adds that order at the end of a price queue, which represents time priority, head of the queue represents the order with highest time priority i.e. the order which comes before all the order below it.

limit order book aggresive ordre data structure.jpeg

Now our goal is to perform the above operation as quickly as possible. If you look at it closely, it involves finding the opposite order of matching the price, which is equal to or less/greater than the specified price, removing the order from the order book if it matched or canceled, adding order into the order book at an appropriate place if not matched.

Rough Solution (LLD-Machine Coding)

Here is a possible low-level design (LLD) for a limit order book in Java:

public class LimitOrderBook {
    private Map<Double, List<Order>> buyOrders;
    private Map<Double, List<Order>> sellOrders;

    public LimitOrderBook() {
        buyOrders = new TreeMap<>(Collections.reverseOrder());
        sellOrders = new TreeMap<>();
    }

    public void addBuyOrder(Order order) {
        double price = order.getPrice();
        if (buyOrders.containsKey(price)) {
            buyOrders.get(price).add(order);
        } else {
            List<Order> orders = new ArrayList<>();
            orders.add(order);
            buyOrders.put(price, orders);
        }
    }

    public void addSellOrder(Order order) {
        double price = order.getPrice();
        if (sellOrders.containsKey(price)) {
            sellOrders.get(price).add(order);
        } else {
            List<Order> orders = new ArrayList<>();
            orders.add(order);
            sellOrders.put(price, orders);
        }
    }

    public void cancelOrder(Order order) {
        double price = order.getPrice();
        if (order.isBuy()) {
            buyOrders.get(price).remove(order);
        } else {
            sellOrders.get(price).remove(order);
        }
    }

    public double getBestBuyPrice() {
        if (buyOrders.isEmpty()) {
            return Double.MAX_VALUE;
        }
        return buyOrders.firstKey();
    }

    public double getBestSellPrice() {
        if (sellOrders.isEmpty()) {
            return Double.MIN_VALUE;
        }
        return sellOrders.firstKey();
    }
}

public class Order {
    private boolean isBuy;
    private double price;
    private int quantity;

    public Order(boolean isBuy, double price, int quantity) {
        this.isBuy = isBuy;
        this.price = price;
        this.quantity = quantity;
    }

    public boolean isBuy() {
        return isBuy;
    }

    public double getPrice() {
        return price;
    }

    public int getQuantity() {
        return quantity;
    }
}

Did you find this article valuable?

Support Subhahu Jain by becoming a sponsor. Any amount is appreciated!