Chat event aggregator: sliding-window message counts and active chats per user

Users can hold conversations in many separate chat sessions. A stream of events describes their activity, and you are asked to build an in-memory aggregator over that stream. Activity counts only inside a sliding time window: an event older than the window no longer counts. The report describes two parts and the operations each one adds. The method signatures below are a reasonable shape for those operations, not quoted from the round. ### Clarifying Questions - What unit do timestamps and the window length use, and is the window fixed for the life of the aggregator? - Roughly how many users, chats and events per second must one instance handle? - Is the aggregator single-threaded, or can events and queries arrive concurrently? ### Part 1 — Message events and a windowed count At first there is one event type: user `u` sends a message in chat `c` at time `t`. The aggregator is created with a window length `W`. Implement: ```python class MessageAggregator: def __init__(self, window: int): ... def add_event(self, user_id: str, chat_id: str, timestamp: int) -> None: ... def count_active(self, user_id: str, chat_id: str, timestamp: int) -> int: ... ``` `count_active` returns how many of that user's message events in that chat fall inside the window that ends at `timestamp`. ```hint What can never matter again For one user and chat, think about which old events can never be counted again once time has moved past them, and how to drop them cheaply. ``` #### Clarifying Questions for this Part - Is the window `(t - W, t]` or `[t - W, t]`: does an event exactly `W` old still count? - Do events arrive in timestamp order, and are query timestamps non-decreasing? - Can a user send several messages in the same chat with the same timestamp? #### What This Part Should Cover - A per-(user, chat) structure with expiry of old events - The time complexity of `add_event` and `count_active` - Bounding memory as pairs go quiet ### Part 2 — End-session events and active chats per user Add a second event type: user `u` ends chat session `c` at time `t`. Support it in `add_event`, and add: ```python def active_chats(self, user_id: str, timestamp: int) -> int: ... ``` `active_chats` returns how many of the user's chats are active at `timestamp`. ```hint State first, then the query Decide what ending a session does to the counts you already keep, then decide whether to compute the per-user number on demand or maintain it as events arrive. ``` #### Clarifying Questions for this Part - What makes a chat active: at least one message inside the window, and not ended since? - After a session ends, can the same chat receive new messages, and do they start a new session? - What should `count_active` return for a chat whose session has ended? #### What This Part Should Cover - A precise definition of an active chat and how an end event changes the stored state - An efficient per-user query that stays correct as messages expire - Extending the Part 1 interface without breaking existing callers ### What a Strong Answer Covers - Pins down window boundaries, ordering assumptions and end-session semantics before coding - Per-pair queues with expiry for the windowed count, with stated time and memory complexity - A clear definition of an active chat and a per-user count that stays correct as events expire - Clean, extensible code with tests for boundary timestamps, ended sessions and reopened chats - A discussion of out-of-order events and cleanup of idle state ### Follow-up Questions - Events can arrive late and out of order, by up to a bounded delay `D`. What changes? - Memory grows because millions of chats go quiet. How do you reclaim it? - How would you shard this aggregator across machines? - A dashboard now needs `count_active` for every chat of one user at once. How would you serve that efficiently?