OpenAI Software Engineer Interview Experience — Three-Part Sliding Window Coding Round

A few days ago I had a technical interview at OpenAI. The coding round had this multi-part problem, so I'm sharing the problem statement and my solution.

Part 1: Recent Interaction Count

Implement an in-memory, single-threaded chat session analytics service. The input is a live interaction log stream whose global ts is non-decreasing. Each log entry has: user: str, chat: int (unique within each user), and ts: int (in minutes).

We often need to query the number of interactions of a given (user, chat) in the past 15 minutes, defined as the closed interval [T-14, T], where T is the largest timestamp that has appeared in the stream.

Implement:

• ingest(user, chat, ts)
• count_recent(user, chat) -> int

Requirements: ts is non-decreasing with no duplicates; log volume and query volume are both large, so both operations must be efficient; memory must be bounded, proportional to the number of chats active in the past 15 minutes rather than to the total history.

Approach

The easy trap is storing everything and filtering at query time, which blows up memory. Use the "non-decreasing" condition:

• Keep a ts deque for each (user, chat) (arrival order is time order).
• Also keep a global deque that stores (ts, key) in arrival order. On every ingest, pop entries with ts < T-14 from the head, and pop the head of the corresponding key's deque at the same time; if a deque becomes empty, delete the key.
• A query just returns len(deque). O(1), zero work at read time.

Every stored event is guaranteed to lie within [T-14, T], so memory is naturally bounded. Amortized O(1) per operation.

Key detail: the window is a closed interval. For example, when T=20 the window is [6, 20], and an event at t=6 still counts.

Part 2: Live Session Count

Events get one more field, kind: touch (the user sends a message and gets a reply) or close (the user explicitly ends the session; it may arrive arbitrarily long afterwards, or never).

We also need to maintain, in real time, each user's current number of live sessions. A session is live if and only if: there is a touch event in the past 15 minutes, and no close event has been received after the latest touch.

• ingest(user, chat, ts, kind="touch")
• count_live(user) -> int

Approach

For each (user, chat), store a deque of (ts, kind). The session state depends on only two things: the time of the latest touch, and whether there is a close with a ts strictly greater than it.

• On touch: it becomes the latest, and the closed flag is cleared (a new touch reactivates the session, overriding any earlier close).
• On close: it only ends the session if close_ts > latest_touch_ts. A close with the same ts doesn't count ("after" means strictly greater).
• Live = the latest touch falls within [T-14, T] and has not been closed.

Expiry is handled lazily: on count_live, sweep that user's chats, delete any chat with no events left in the window (so memory stays bounded), and count the live ones. The write path doesn't need a global scan.

Example: t=2 touch -> 1; t=8 close -> 0.

Part 3: Out-of-Order Arrival

The third part relaxes one assumption: events may now arrive out of order (a ts can be smaller than ones already processed). The T seen by queries is still non-decreasing, and cleanup can be done at query time.

Approach

The core insight: T never goes backwards, so anything evicted at query time can never enter a window later, which makes lazy cleanup safe.

• ingest only records: for each key, a sorted list of touch times (insert with bisect), and for each key, the max close timestamp. Anything that is already < T-14 on arrival is dropped directly (it can never enter a future window).
• At query time: binary-search to drop expired touches, delete dead chats, then count. The latest touch is the tail of the list (it is kept sorted); closed = max_close > latest.

A late close (with ts greater than the latest touch) correctly marks the session as not live; a late touch (with ts greater than the recorded close) reactivates it. There's no need to replay like you would with an out-of-order ledger. Comparing two numbers (max touch ts vs. max close ts) is enough.

For Part 3 I checked against a brute-force implementation using randomly generated out-of-order streams (counts plus per-user live counts), and everything matched.

Common Pitfalls

1. The window is the closed interval [T-14, T], not [T-15, T]. Off by one minute and the sample won't pass.
2. "A close after the latest touch" is strictly greater: a close with the same ts does not end the session.
3. A new touch clears any earlier close, so a session can be reactivated.
4. Memory bound: Part 1 uses a global arrival-order queue to drive expiry; Part 3 relies on the monotonic T to clean up at query time. Say which one you use and why.
5. T is global (the max over the whole stream), not per user. Other users' events push your window forward.

Code

from bisect import bisect_left, insort
from collections import defaultdict, deque

WINDOW_MINUTES = 15  # window spans 15 minute marks, inclusive on both ends

# ---------------------------------------------------------------------------
# Part 1: globally non-decreasing event stream, no duplicates.
# ---------------------------------------------------------------------------
class WindowedEventCounter:
    """Sliding-window counts with bounded memory.

    State is proportional to chats with events in the current window, never
    to total history: a global arrival-ordered log drives eviction, so every
    stored event lies inside [now-14, now].
    """

    def __init__(self):
        self._now = 0                        # largest timestamp seen
        self._streams = defaultdict(deque)   # (user, chat) -> deque of ts
        self._arrivals = deque()             # (ts, key) in arrival order

    def _tick(self, ts):
        self._now = max(self._now, ts)
        start = self._now - WINDOW_MINUTES + 1
        while self._arrivals and self._arrivals[0][0] < start:
            _, key = self._arrivals.popleft()
            q = self._streams[key]
            q.popleft()  # arrival order == time order; the expired one is head
            if not q:
                del self._streams[key]

    def ingest(self, user: str, chat: int, ts: int) -> None:
        key = (user, chat)
        self._streams[key].append(ts)
        self._arrivals.append((ts, key))
        self._tick(ts)

    def count_recent(self, user: str, chat: int) -> int:
        # `now` only moves in ingest(), which already evicted; nothing to do.
        return len(self._streams.get((user, chat), ()))

# ---------------------------------------------------------------------------
# Part 2: events gain a kind ("touch" | "close").
# A session is live iff it has a touch within [now-14, now] AND no close
# event strictly after its latest touch.
# ---------------------------------------------------------------------------
class LiveSessionCounter(WindowedEventCounter):
    def __init__(self):
        super().__init__()
        self._streams = defaultdict(deque)  # (user, chat) -> deque of (ts, kind)
        self._chats_of = defaultdict(set)   # user -> set of chat keys

    def ingest(self, user: str, chat: int, ts: int, kind: str = "touch") -> None:
        key = (user, chat)
        self._streams[key].append((ts, kind))
        self._arrivals.append((ts, key))
        self._chats_of[user].add(key)
        self._tick(ts)

    def _is_live(self, key) -> bool:
        """Liveness of one chat against the current window. Caller sweeps."""
        q = self._streams.get(key)
        if not q:
            return False
        start = self._now - WINDOW_MINUTES + 1
        latest_touch, closed = None, False
        for ts, kd in q:  # part 2: arrival order == time order
            if kd == "touch":
                latest_touch, closed = ts, False  # newer touch clears old close
            elif latest_touch is not None and ts > latest_touch:
                closed = True  # strictly after the latest touch
        return (latest_touch is not None
                and latest_touch >= start
                and not closed)

    def count_live(self, user: str) -> int:
        n = 0
        for key in list(self._chats_of[user]):
            if not self._streams.get(key):
                self._chats_of[user].discard(key)  # nothing in-window; drop
                continue
            n += self._is_live(key)
        return n

# ---------------------------------------------------------------------------
# Part 3: events may arrive out of order (older timestamps
# possible). Queries still observe non-decreasing `now`. Cleanup is deferred
# to query time — safe because `now` never moves backward, so anything
# evicted can never re-enter a future window.
# ---------------------------------------------------------------------------
class ReorderedEventTracker:
    def __init__(self):
        self._now = 0
        self._touches = defaultdict(list)  # (user, chat) -> sorted ts list
        self._last_close = {}              # (user, chat) -> max close ts
        self._chats_of = defaultdict(set)

    def _start(self):
        return self._now - WINDOW_MINUTES + 1

    def ingest(self, user: str, chat: int, ts: int, kind: str = "touch") -> None:
        self._now = max(self._now, ts)
        if ts < self._start():
            return  # already expired; can never fall in a future window
        key = (user, chat)
        if kind == "touch":
            insort(self._touches[key], ts)
        else:
            self._last_close[key] = max(ts, self._last_close.get(key, float("-inf")))
        self._chats_of[user].add(key)

    def _prune(self, key) -> bool:
        """Evict expired touches; drop the chat if nothing in-window remains."""
        lst = self._touches.get(key)
        if lst:
            del lst[:bisect_left(lst, self._start())]
            if not lst:
                del self._touches[key]
        if key not in self._touches:
            self._last_close.pop(key, None)
            return False
        return True

    def count_recent(self, user: str, chat: int) -> int:
        key = (user, chat)
        if not self._prune(key):
            self._chats_of[user].discard(key)
            return 0
        return len(self._touches[key])

    def count_live(self, user: str) -> int:
        n = 0
        for key in list(self._chats_of[user]):
            if not self._prune(key):
                self._chats_of[user].discard(key)
                continue
            latest = self._touches[key][-1]  # list kept sorted
            if not self._last_close.get(key, float("-inf")) > latest:
                n += 1
        return n

Happy to discuss if you have questions.