Count Orders in the Last 30 Minutes

Problem Design a structure that ingests orders with their timestamps and answers "how many orders were placed in the last 30 minutes?" — ideally in O(1) per query.

Input / Output

• Input: a stream of record(timestamp) calls, interleaved with count(now) queries.
• Output: for each query, the number of orders with timestamp > now - 30min.

Constraints

• Orders arrive continuously; the stream is unbounded, so retaining everything forever is not acceptable.
• Orders older than 30 minutes must not be counted and ideally should not be stored.
• Timestamps are non-decreasing (a reasonable clarifying assumption — out-of-order arrival changes the design).

Example

• Orders arrive at t = 0, 5, 10, ..., 40 minutes. A query at t = 40 counts only orders with timestamp > 10, i.e. those at 15, 20, 25, 30, 35, 40 -> 6.
• Tricky case: a burst of 1M orders that all age out at once makes a lazy-eviction design do 1M units of work on a single unlucky query — amortised O(1), but a bad tail latency.