Coding
Order Books

Fills Against a Resting Book

Difficulty

Asked at IMC Trading, Hudson River Trading

Theory: Order Books and Matching

Read the problem, hints and solution here. The editor needs a bigger screen: open this page on a laptop to write and run your code.

Available in Python and C++. You are solving it in C++. Switch to Python

Implement fill_order(levels, qty, limit_price, side). It takes an incoming order, walks the resting side of the book, and works out what the order trades against.

  • levels is the resting opposite side, already in book order, best price first. Each entry is a price and an available quantity, in integer ticks and lots. For a buy these are asks in ascending price; for a sell they are bids in descending price.
  • qty is the incoming quantity, a non-negative integer.
  • limit_price bounds what the order will accept: a buy will not pay above it, a sell will not accept below it.
  • side is 'B' for a buy or 'S' for a sell.

Walk the levels in order, consuming as much as the incoming order still needs at each. A level may be consumed partially, leaving the rest resting.

Return the fills and the remaining quantity: the fills are the (price, quantity) pairs actually traded, in the order they occurred, and remaining is the unfilled quantity.

std::pair<std::vector<std::pair<long long, long long>>, long long> fill_order(
    const std::vector<std::pair<long long, long long>>& levels,
    long long qty, long long limit_price, char side);

Each level is {price, available}, side is 'B' or 'S', and the result is {fills, remaining} with each fill a {price, quantity} pair.

Examples

fill_order({{100, 5}, {101, 10}, {102, 7}}, 12, 101, 'B');
// {{{100, 5}, {101, 7}}, 0}

fill_order({{100, 5}, {101, 10}}, 20, 100, 'B');
// {{{100, 5}}, 15}

fill_order({}, 5, 100, 'B');
// {{}, 5}

fill_order({{100, 5}}, 0, 100, 'B');
// {{}, 0}

The first fills 5 at the touch and 7 of the 10 at the next level, leaving 3 resting there. The second cannot pay 101, so it stops after the first level with 15 lots unfilled. The last two trade nothing, so each returns an empty fills list and the whole incoming quantity as remaining.

Constraints

  • 0 <= levels.size() <= 2 * 10^5. The hidden performance case calls the function 100,000 times on the full book.
  • Quantities and prices are positive integers.
  • Levels are monotone in price, so once a level is out of reach of the limit price, every later one is too. Stop rather than skipping.
  • When nothing trades, return {{}, qty}: an empty fills vector, and the whole incoming quantity as remaining.
  • An empty book, a zero-quantity order and a best level already out of reach of the limit price all take that path, and none of them is an error.
  • Do not emit zero-quantity fills.
Terms used in this problem (9)
order book:
The list of resting orders to buy and sell at each price. Bids sit below the current price, asks above it, and each side is kept in price order.
bid:
A resting order to buy, or its price. The best bid is the highest price anyone will pay right now.
ask:
A resting order to sell, or its price, also called the offer. The best ask is the lowest price anyone will sell at right now.
touch:
The best bid and the best ask together: the top price on each side of the book. A fill at the touch trades at the best price.
tick:
The smallest step a price can move. Prices in these problems are integers counted in ticks, so there is no rounding.
lot:
The unit of quantity. Orders and fills are counted in whole lots.
resting order:
An order sitting in the book, waiting for someone to trade against it. It stays until it is filled or cancelled.
limit order:
An order to buy at or below a given price, or to sell at or above it. If it cannot trade at once, it rests in the book.
fill:
A trade that executes part or all of an order, at one price and one quantity. A partial fill leaves the rest of the order resting.
Rate this problem
Language:
Python 3.12C++23
fill_order
Rate this problem