~/problems / Streams & durability / Rolling windows and rate counters

OA: Chat message events aggregation

easy 3 levels ~20 min OpenAI

Level 1 Per-user counts over a sliding window, with bounded memory

A chat backend wants live counters of how many messages each user sent recently. The service runs for months, so it must forget old events. Build ChatEventAggregator:

  • ChatEventAggregator(m: int): the window length in seconds, m >= 1.
  • record(user_id: str, chat_id: str, timestamp: int) -> None: one message from user_id in chat_id at timestamp (whole seconds).
  • count(user_id: str, timestamp: int) -> int: how many messages user_id sent in the window [timestamp - m + 1, timestamp] (both ends included).
  • stored_events() -> int: how many events the aggregator is currently keeping.

Guarantees about the calls:

  • The timestamp arguments of all record and count calls, taken together in call order, never decrease (it is a live clock).
  • A single user never records twice in the same second (different users can).

Memory rule. After any call with timestamp T, the aggregator must have dropped every event with timestamp <= T - m, for all users, including users who are never mentioned again. stored_events() therefore equals the number of recorded events with timestamp in [T - m + 1, T], where T is the latest timestamp seen (0 before any call). Don't keep empty per-user entries around either.

agg = ChatEventAggregator(10)
agg.record("u1", "c1", 1)
agg.record("u2", "c1", 3)
agg.record("u1", "c2", 5)
agg.count("u1", 5)       # 2
agg.count("u1", 10)      # 2    window [1, 10]
agg.count("u1", 11)      # 1    window [2, 11]: the event at 1 is gone
agg.stored_events()      # 2    (u2@3 and u1@5)
agg.count("u3", 13)      # 0
agg.stored_events()      # 1    (u2@3 expired at T = 13 even though nobody asked about u2)
agg.count("u1", 15)      # 0
agg.stored_events()      # 0

count must be O(1) amortised: don't scan a user's events on every call.

Show hint

Keep one queue of all events in time order, plus a dict user -> number of events in the window. Every call first pops expired events off the front of the queue (decrementing, and deleting at zero, their user's counter). Each event is pushed and popped once, so the cost is O(1) amortised.

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Topic: Rolling windows and rate counters. QPS over the last N seconds, hit counters, rate limiters.

0:00
Ctrl ' run · Ctrl ↵ submit
esc