Reconstruct the prevailing spread at each trade

Question

You have three time-sorted streams: trades (ts, price), best-bid updates (ts, bid), and best-ask updates (ts, ask). For every trade, recover the prevailing best bid and best ask (each the latest update at or before the trade) and report the spread ask - bid at execution time. This is how effective-spread and price-improvement stats are built when the bid and ask arrive as two independent feeds.

bids   = [(1, 99.9), (4, 100.1)]
asks   = [(2, 100.2), (5, 100.4)]
trades = [(3, 100.0), (6, 100.3)]
->
[(3, 100.0, 99.9, 100.2, 0.3),      # last bid ts=1, last ask ts=2
 (6, 100.3, 100.1, 100.4, 0.3)]     # last bid ts=4, last ask ts=5

Implement the three-way join in $O(n + b + a)$ , one pass over each stream.

Accepted Answer

This is two independent as-of joins running in lockstep. Keep one forward-only pointer into the bid stream and one into the ask stream; for each trade, advance each pointer through every update at or before the trade, caching the last value seen. Both pointers are monotone because trades are sorted, so no rewinding is ever needed. Tracing the example: the trade at ts=3 sees bid from ts=1 (99.9) and ask from ts=2 (100.2), spread 0.3; the trade at ts=6 sees bid from ts=4 (100.1) and ask from ts=5 (100.4), spread 0.3. Time O(n + b + a): each of the three streams is scanned once. Space O(1) beyon…

Reconstruct the prevailing spread at each trade

Your answer

More Coding questions