Asked at IMC Trading, Hudson River Trading
Theory: Order Books and MatchingRead 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 Python. Switch to C++
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.
def fill_order(
levels: list[tuple[int, int]],
qty: int,
limit_price: int,
side: str,
) -> tuple[list[tuple[int, int]], int]: ...
Each level is (price, available) and the result is (fills, remaining),
with fills a list of (price, quantity) tuples.
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.
0 <= len(levels) <= 2 * 10^5.([], qty): an empty fills list, and the whole
incoming quantity as remaining.