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 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.
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 <= levels.size() <= 2 * 10^5. The hidden performance case calls the
function 100,000 times on the full book.{{}, qty}: an empty fills vector, and the
whole incoming quantity as remaining.