You must report the volume-weighted average price over the trailing 5 minutes, updated on every trade, with trades arriving out of order by up to 50 milliseconds. Give a structure with O(1) amortised update and say what the out-of-order arrivals force you to change.

You must report the volume-weighted average price over the trailing 5 minutes, updated on every trade, with trades arriving out of order by up to 50 milliseconds. Give a structure with O(1) amortised update and say what the out-of-order arrivals force you to change.

Approach: A running sum over a deque handles in-order arrivals. Decide what a late trade does to a figure already published, and how a small bounded delay avoids a general order-statistic structure.

A ring buffer of trades keyed by timestamp plus two running sums, published behind a watermark of 50 milliseconds, giving O(1) amortised per trade. Maintain the sum of price times size and the sum of size, add each arriving trade to both, and evict from the front while the front timestamp is older than the window, which is O(1) amortised because each trade is added once and evicted once. Out-of-order arrivals break the assumption that the buffer is sorted, so insert into the correct slot, which stays O(1) expected while lateness is bounded at 50 milliseconds since only the last few entries can move, and publish only windows that end before now minus 50 milliseconds. Without that watermark a late trade restates a figure already sent downstream. Repeated addition and subtraction on a running sum accumulates floating point drift over millions of updates, so accumulate in integer ticks times integer size, or rebuild the window from the buffer on a fixed schedule.

Follow-up: How do you serve the same window over 8000 symbols with a single thread and a fixed memory budget?

Key concepts: ring buffer, running sum, watermark, floating point drift.