Bucket trades by quote regime

Question

You have two time-sorted streams: quote-update timestamps quote_ts (each marks when a new quote took effect) and trade timestamps trade_ts. Each trade printed under exactly one prevailing quote, the quote that was live when it executed. Count how many trades fall into each quote regime: the half-open interval [quote_ts[i], quote_ts[i+1]), plus a leading bucket for trades that printed before the first quote.

quote_ts = [2, 5, 9]
trade_ts = [1, 3, 4, 5, 7, 10, 11]
->
[1, 2, 2, 2]
# bucket 0 (before ts=2): {1}          -> 1
# bucket 1 ([2, 5)):       {3, 4}      -> 2
# bucket 2 ([5, 9)):       {5, 7}      -> 2
# bucket 3 ([9, inf)):     {10, 11}    -> 2

Return the per-regime counts in $O(n + m)$ , one pass over each stream.

Accepted Answer

This is a merge-join that produces group counts instead of paired rows. Walk the trades in order, carrying a forward-only pointer qi into the quote timestamps. For each trade, advance qi past every quote that took effect at or before the trade; then qi is exactly the index of the regime the trade belongs to, so increment that bucket. Because both streams are sorted, qi never moves backward. Tracing the example: t=1 stays in bucket 0; t=3 and t=4 land in bucket 1 (after passing the ts=2 quote); t=5 advances past the ts=5 quote into bucket 2 (the interval is [5, 9), so a trade at exactly 5 is u…

Bucket trades by quote regime

Your answer

More Coding questions