Count Orders in Last 30 Minutes in O(1)

Problem: Design a system that ingests orders along with their timestamp, and supports a query to retrieve the number of orders placed in the last 30 minutes, ideally in O(1) time per query.

Constraints: Orders arrive continuously (streaming); old orders (older than 30 minutes) should not count.

Example: If orders arrive at t=0,5,10,...,40 minutes, a query at t=40 should count only orders with timestamp > 10 (i.e., within the last 30 minutes).

Approach: Maintain a sliding-window counter: keep a running count and a queue/deque of timestamps; on each new order, increment the count and push its timestamp; before answering a query (or lazily on each insert), pop and decrement for any timestamps older than (now - 30min) from the front of the deque. Because each entry is pushed and popped at most once, amortized cost per operation is O(1); if a strict worst-case O(1) is required regardless of burst eviction, a bucketed/rolling-counter approach (per-minute buckets summed over a 30-entry ring buffer) can bound work per operation.