Sliding-Window Chat Analytics: Recent Counts, Live Sessions, Out-of-Order Events

Build an in-memory, single-threaded analytics service for chat sessions. It consumes a real-time stream of interaction log records, and each record has three fields: - `user: str`, the user; - `chat: int`, a chat id that is unique only within its user, so a chat is identified by the pair `(user, chat)`; - `ts: int`, the time of the interaction in whole minutes. Let `T` be the largest timestamp that has appeared anywhere in the stream so far. "The past 15 minutes" means the closed interval `[T - 14, T]`. For example, when `T = 20` the window is `[6, 20]`, and an event at minute 6 still counts. The problem has three parts, and each part extends or relaxes the one before it. Write working code for each part, and state the time and memory cost of every operation. ### Constraints and Clarifications - `T` is global: it is the maximum over every user's events, not a per-user value. An event from another user can move the window forward and expire your chat's events. - Ingestion and queries both arrive at high volume, so both must be efficient. - Memory must stay bounded: proportional to the number of chats with activity in the past 15 minutes, not to the total history of the stream. - Everything runs in one process on one thread; nothing needs to be persisted. ### Clarifying Questions - Can one chat have several distinct events in the same minute, and does each of them count? - Is amortized constant time per operation acceptable, or must every individual call be constant time? - What should a query return before any event has arrived, or for a chat or user that has never appeared? ### Part 1 — Recent interaction count Implement: - `ingest(user: str, chat: int, ts: int) -> None`, which records one interaction; - `count_recent(user: str, chat: int) -> int`, which returns the number of interactions of chat `(user, chat)` within `[T - 14, T]`. In this part, timestamps arrive in non-decreasing order across the whole stream, and the stream contains no duplicate records. Ingests and queries interleave arbitrarily. ```hint Next to leave Ask what the non-decreasing order tells you about which stored event will be the next one to leave the window. ``` ```hint A chat nobody asks about A chat can receive a burst of events and never be queried again. Decide what removes its state, so that memory follows the active chats rather than the queries. ``` #### What This Part Should Cover - The closed window boundary and the global definition of `T` - The cost of `ingest` and `count_recent`, amortized or worst case - What triggers eviction, and why memory is bounded by the chats active in the window - Behavior when one chat receives many events in the same minute ### Part 2 — Live sessions per user Each event now carries a fourth field, `kind`: - `"touch"`: the user sent a message in the chat and received a reply; - `"close"`: the user explicitly ended the session. A close may arrive arbitrarily long after the session's last touch, or never. A chat session is live if and only if both of the following hold: 1. it has at least one touch within `[T - 14, T]`; 2. no close has been received whose timestamp is strictly greater than the chat's latest touch. So a new touch reactivates a closed session, and a close with the same timestamp as the latest touch does not end it. For example, a touch at minute 2 makes the user's live count 1, and a close for the same chat at minute 8 brings it back to 0. Implement: - `ingest(user: str, chat: int, ts: int, kind: str = "touch") -> None`; - `count_live(user: str) -> int`, the number of the user's sessions that are live at the current `T`. Timestamps are still non-decreasing in this part. ```hint What liveness depends on List which facts about a chat's history can still change whether it is live. Most of the history turns out not to matter. ``` ```hint A change without an event A live session can stop being live even though no event arrives for that chat. Decide how and when your structure notices. ``` #### Clarifying Questions for this Part - Should `count_recent` still be supported, and if so, does a close count as an interaction? - Must `count_live` take constant time, or is a cost proportional to the user's recently active chats acceptable? #### What This Part Should Cover - The minimal per-chat state that decides liveness, including the strict tie rule between a close and the latest touch - Reactivation by a new touch, and closes for chats with no touch in the window - How live sessions expire as `T` advances, and the resulting cost of `count_live` - A memory bound that still follows the recently active chats ### Part 3 — Out-of-order arrival Relax one assumption: events may now arrive out of order, so an event's `ts` can be smaller than timestamps that were already processed. `T` is still the largest timestamp seen so far, so it never decreases from one query to the next, and you may defer cleanup to query time. Both `count_recent(user, chat)` and `count_live(user)` must stay correct under the definitions above, with "after the latest touch" decided by timestamps rather than by arrival order. For example, a close that arrives late but carries a timestamp greater than the chat's latest touch ends the session, and a late touch whose timestamp is greater than every close of that chat reactivates it. ```hint The right edge never moves back Because `T` only grows, think about what an event can still contribute once it is older than the window, whether it arrives that way or ages into it. ``` ```hint A close before its touch Trace a close for a chat that has no touch in the window yet, followed by a late touch with an earlier timestamp. Check that your cleanup keeps what that case needs. ``` #### Clarifying Questions for this Part - Is there a bound on how late an event can arrive? - Is cleanup at query time enough even for users who are never queried again, or must memory stay bounded whatever the query pattern? #### What This Part Should Cover - Why discarding already-expired arrivals and deferring eviction to queries are safe - Per-chat state that accepts late events and applies the timestamp-based close rule - The cost of `ingest`, `count_recent` and `count_live`, and when memory is bounded - How correctness is verified against the definitions ### What a Strong Answer Covers - Exact semantics: a closed 15-minute window, a global `T`, and the strict close-after-touch rule - Efficient ingestion and queries, with the cost of each operation stated for each part - An explicit memory argument for each part that names the mechanism releasing state - Edge cases: the boundary minute, same-minute events, a close equal to the latest touch, reactivation, unknown chats and users - Correct, readable code and a way to test it ### Follow-up Questions - How would you make `count_live` constant time in Part 3, with memory bounded no matter which users are queried? - One chat receives thousands of events per minute. How do time and memory behave in each part, and how would you make them independent of the event rate? - How would you test Part 3 so that you trust it on adversarial arrival orders? - The window length becomes a parameter, or timestamps switch from minutes to milliseconds. What changes in your design?