Forward as-of join for markout
Asked at Two Sigma, Citadel
You have two time-sorted streams: trades (ts, price) and quotes (ts, mid). This time you want the next quote, the earliest quote with quote_ts >= trade_ts. This "forward as-of join" is the primitive behind markout: to measure how the mid moved right after your fill, you align each trade to the quote at or after it (or at a fixed horizon).
quotes = [(2, 100.0), (5, 101.0), (9, 103.0)]
trades = [(1, 100.2), (5, 100.9), (6, 101.2), (10, 99.0)]
->
[(1, 100.2, 100.0), # first quote at ts>=1 is ts=2
(5, 100.9, 101.0), # ties: quote at ts=5 counts (at-or-after)
(6, 101.2, 103.0), # next quote at ts>=6 is ts=9
(10, 99.0, None)] # no quote at or after ts=10
Implement the forward join in , one pass over each stream.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.