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 , one pass over each stream.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.