Quant Memo
Coding/●●●●

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 O(n+m)O(n + m), one pass over each stream.

Your answer

This one is open-ended. Work it through, then check your reasoning against the full solution.

More Coding questions