15 minute chat window, one innocent queue, and the follow-up that changes the whole solution.
Imagine finishing the counter before the interviewer has finished their coffee. Append each timestamp, remove the old ones, return the count. You even remembered the boundary case, so this is feeling pleasantly manageable.
Then one requirement changes: messages can arrive late.
Your code still runs.
Its numbers still look believable.
But an expired event can now sit behind a newer one, quietly surviving the cleanup that was supposed to remove it.
This is why I like questions that change one assumption halfway through. They reveal whether we understand the structure we chose, or just recognize the shape of a familiar problem.
Let’s work through a reported OpenAI chat-analytics question. We’ll count recent interactions, track live sessions, and handle events arriving out of order. By the end, you’ll have a complete Python implementation and a small set of cases you can explain without trusting the code.
First, agree on what the counter actually means
Each record contains a user, a chat ID, and a timestamp in whole minutes. A chat ID is unique only within its user, so our key is the pair (user, chat). Ava’s chat 7 and Ben’s chat 7 are different conversations.
Here is the detail worth circling: T is the largest timestamp seen anywhere in the stream. It is global, and it never moves backward.
At T = 20, the recent window is [6, 20]. Both ends count. That is 15 integer minutes, which means the cutoff is T − 14, not T − 15.
If Ben sends an event at minute 21, everyone’s window becomes [7, 21]. Ava’s interaction at minute 6 expires even if nobody has opened her chat again.
Also, this clock advances when an event advances T. Waiting fifteen minutes on your laptop does nothing by itself. A wall-clock expiration policy would be a different contract.
For this walkthrough, each touch is a distinct interaction, including multiple touches in the same minute. Close events affect liveness but do not increase the interaction count. Unknown chats and users return zero. We’ll keep both query methods throughout the exercise.
If you want to try the prompt before seeing the approach, the three-part chat analytics question is readable without unlocking it.
While time arrives in order, a queue earns its place
Start with the easier version: timestamps arrive in nondecreasing order across the entire stream.
Now the oldest stored timestamp really is the next one to expire. A global queue can remove expired entries from the front while a dictionary keeps each chat’s current total. Queries read that total directly.
I prefer aggregating each chat’s events within a minute before storing them. One thousand touches at minute 12 can become one bucket with count 1,000. Keeping one queue entry per event would make memory follow traffic volume, which misses the requirement to bound it by recently active chats.
On ingestion, advance T, evict expired minute buckets globally, and update the affected chat totals. With hash maps and a fixed 15-minute window, that gives expected amortized constant-time ingestion and constant-time count queries. One call can still do substantial cleanup after a large time jump; amortized does not mean every call is equally cheap.
There is a second trap here: cleaning only the chat being queried. Quiet chats would keep their old state forever. Cleanup belongs to the advancing global window, including for chats nobody asks about again.
Now let a timestamp cut the line
Suppose one chat receives timestamps in this arrival order: 20, 8, 19. At T = 20, all three still belong to the window.
Another user then sends an event at 24. The window moves to [10, 24], so our first chat should have two recent interactions: 20 and 19.
But a queue that checks only its front sees 20, decides nothing needs removing, and leaves 8 in the middle. Returning the queue length produces three.
The problem is the ordering assumption. Fast operations do not make that assumption true.
We can sort or use an ordered structure, but the prompt offers a simpler advantage: only fifteen distinct minute values can be relevant at once. Store counts by minute, and expiration no longer depends on arrival order.
Late events outside the current window can be ignored immediately. Since T never decreases, they cannot become recent again.
A session needs more than an open or closed flag
The next requirement adds two event kinds: touch and close.
A session is live when it has a touch inside the current window and no close has a timestamp strictly greater than its latest touch. Equal timestamps leave the session live. Yes, that tie rule deserves its own example.
For one chat, let these records arrive in this order:
Close at 12: no touch exists, so the live count is zero. Keep the close record.
Touch at 10: it arrived later, but happened earlier. The close at 12 still wins, so the live count stays zero.
Touch at 12: the timestamps tie. The session becomes live because the close is not strictly later.
Touch at 14: this touch is newer than the close. The session remains live.
A single Boolean updated in arrival order cannot express that rule reliably. We need timestamps to decide what wins.
Here is my favorite slightly sneaky detail: a chat with zero touches can still have useful state. Delete that close-at-12 record immediately, and the late touch at 10 will incorrectly reopen the session.
Keep close-only records while their timestamps are in the window. Once a close is older than the cutoff, it cannot defeat any touch that still qualifies, so it is safe to remove.
Build around the minute buckets
Our final implementation handles all three stages, including arbitrary arrival order. Rather than maintaining three separate versions, it uses the stronger representation from the start.
For each chat, store at most fifteen minute entries. Each entry contains a touch count and whether a close occurred in that minute. Repeated closes at the same timestamp need only one Boolean because their multiplicity cannot change liveness.
A second map runs in the other direction: minute → chat keys with an entry there. This is our cleanup index. When a minute expires, we know exactly which chats need updating.
After each ingestion, refresh the summaries only for affected chats. Each refresh examines at most fifteen entries, calculates the recent touch total, and compares the latest touch with the latest close.
We also maintain a live-chat set and a per-user live count. Update the user count only when a chat switches between live and not live. Ten messages in one already-live session must not turn into ten live sessions.
The complete implementation
This is a single-threaded, in-memory implementation for valid integer-minute timestamps. It assumes distinct touch events, not a retrying delivery system with duplicate event IDs.
class ChatAnalytics:
W = 15
def __init__(self):
self.T = None
self.chats = {} # key -> minute -> [touches, close]
self.buckets = {} # minute -> set of chat keys
self.recent = {} # key -> touch count
self.live = set() # live chat keys
self.by_user = {} # user -> live session count
def ingest(self, user, chat, ts, kind='touch'):
if kind not in ('touch', 'close'):
raise ValueError('Unknown event kind')
self.T = ts if self.T is None else max(self.T, ts)
cutoff = self.T - self.W + 1
changed = set()
# There are at most W stored minute buckets.
for minute in list(self.buckets):
if minute < cutoff:
for key in self.buckets.pop(minute):
del self.chats[key][minute]
changed.add(key)
if ts >= cutoff:
key = (user, chat)
minutes = self.chats.setdefault(key, {})
cell = minutes.setdefault(ts, [0, False])
if kind == 'touch':
cell[0] += 1
else:
cell[1] = True
self.buckets.setdefault(ts, set()).add(key)
changed.add(key)
for key in changed:
self._refresh(key)
def _refresh(self, key):
minutes = self.chats[key]
total = sum(n for n, closed in minutes.values())
touches = [t for t, (n, c) in minutes.items() if n]
closes = [t for t, (n, c) in minutes.items() if c]
latest_touch = max(touches, default=None)
latest_close = max(closes, default=None)
now_live = latest_touch is not None and (
latest_close is None or latest_touch >= latest_close
)
was_live = key in self.live
if now_live != was_live:
user = key[0]
delta = 1 if now_live else -1
count = self.by_user.get(user, 0) + delta
if count:
self.by_user[user] = count
else:
self.by_user.pop(user, None)
if now_live:
self.live.add(key)
else:
self.live.remove(key)
if total:
self.recent[key] = total
else:
self.recent.pop(key, None)
if not minutes:
del self.chats[key]
def count_recent(self, user, chat):
return self.recent.get((user, chat), 0)
def count_live(self, user):
return self.by_user.get(user, 0)
Notice the order inside ingest: advance global time, remove expired entries, accept the new event if it still qualifies, then refresh affected chats. We never expose an intermediate summary because the service is single-threaded.
Both queries are plain dictionary lookups. They do not advance time, scan history, or create state for an unknown user.
Memory argument is part of the answer
Let W be the number of discrete minutes in the window, and A the number of chats with any retained touch or close. Here, W = 15.
Memory: O(W × A). Each chat has at most W minute entries. The reverse index contains references to those same chat-minute pairs. Empty chats and zero user totals are removed.
Queries: expected O(1). Both results are maintained during ingestion, using hash maps.
Ingestion: expected amortized O(W). Scanning the minute index costs at most O(W). Each chat-minute entry is inserted and eventually removed once, and an affected chat refresh costs O(W). For fixed W = 15, that is amortized constant time.
One expensive ingestion: O(W × A). A large timestamp jump can expire nearly everything at once. That cost belongs to the call that advances time; it has not disappeared.
These bounds use the usual model where hash operations and counter arithmetic have constant expected cost. They describe algorithmic work, not a measured latency benchmark.
If timestamps become milliseconds, please do not casually call W small. Fifteen minutes would contain 900,000 possible millisecond values. At that point, sparse ordered structures, coarser buckets, or a changed precision requirement deserve a fresh discussion.
Make the example disagree with your first guess
Before feeling pleased with the implementation, write expected answers by hand. These are the cases I would put beside the editor:
Boundary: at T = 20, a touch at 6 counts and a touch at 5 does not.
Global time: Ava touches at 6; Ben touches at 21. Ava’s recent count and live count become zero.
Same minute: three distinct touches at 12 produce recent count three and live count one.
Timestamp tie: a touch and close at 12 leave the session live, whichever arrives first.
Late touch: close at 12 followed by touch at 10 leaves the session closed.
Late close: touch at 10, then another user advances T to 20, then close at 12 arrives. The first session becomes closed.
Isolation: Ava’s chat 7 never contributes to Ben’s chat 7.
Large jump: an event at 100 removes all state from minutes 85 and earlier, including chats that have never been queried.
For a stronger check, keep a deliberately slow reference implementation that retains every event. After each arrival, recompute T, filter by the definition, and compare both query answers. Feed the same event set in different orders and compare after each prefix against the reference for that prefix.
That last qualification matters: different prefixes contain different evidence. Matching only the final totals can miss a wrong answer in the middle.
Where the interview model stops
In a production stream, event time and processing time are different clocks. Systems also need policies for how long to wait and what to do with late data. The Apache Beam guide on watermarks and late data explains that distinction.
Our maximum observed timestamp is not proof that every earlier event has arrived. It only defines this exercise’s current window. A late event inside that window can still change the answer.
Retries would introduce another requirement: event identity. Without an ID, two identical-looking touches might be two legitimate interactions or one interaction delivered twice. The current prompt lets us count them as distinct; a real service needs an explicit policy.
For your next practice session, give yourself one concrete deliverable: explain why the close-at-12 record must survive before the touch-at-10 record arrives. Then implement the counter and trace a global time jump without looking at the solution.
I like this exercise because the useful habit travels with you. Dashboards, chat sessions, activity feeds, and monitoring systems all ask us to decide which facts still matter. Once you can explain that decision, choosing the data structure becomes much less mysterious.
If this kind of illustrated walkthrough helps, follow me for the next one. And tell me which detail you spotted first: the inclusive boundary, the global clock, or the close that arrived before its touch?
~ Emily
Top comments (0)