Quant Memo
Coding/●●●●

As-of join with a staleness cap

Asked at Jane Street, Optiver

You have two time-sorted streams: trades (ts, price) and quotes (ts, mid). As before, each trade should carry the latest quote with quote_ts <= trade_ts. But a quote older than a tolerance tau is considered stale: if the freshest available quote is more than tau seconds old, report None instead of a misleadingly precise mark. Real systems always add this guard so a frozen or gapped feed does not silently poison slippage numbers.

tau = 4
quotes = [(1, 100.0), (2, 100.5), (12, 102.0)]
trades = [(3, 100.2), (7, 100.4), (13, 101.9)]
->
[(3, 100.2, 100.5),     # prevailing quote ts=2, age 1 <= 4
 (7, 100.4, None),      # prevailing quote still ts=2, age 5 > 4, stale
 (13, 101.9, 102.0)]    # prevailing quote ts=12, age 1 <= 4

Implement the staleness-guarded as-of 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