Unique Users in Sliding Buffer

MediumPython

Problem

Interface.ai's conversational banking assistant emits an event stream as (userId, time) pairs. Given a buffer size k, determine the unique users represented in the buffer after each event arrives, where the buffer contains the most recent k events.

Implement unique_users_in_buffers(events, k). Return one result for every input event. Before the buffer reaches size k, use all events seen so far. Each result must contain unique user IDs in their first appearance order within the current buffer.

Formal Specification

Input: events, a list of pairs [userId, time], and positive integer k.
userId is a string, and time is an integer. Events are provided in nondecreasing timestamp order, but timestamps may repeat.
Output: A list of lists. The element at index i contains the distinct user IDs in the buffer after processing events[i], ordered by first appearance in that buffer.
The original input must not be modified.

Constraints

1 <= len(events) <= 10^5
1 <= k <= len(events)
Each event has the form [userId, time]
User IDs are nonempty strings
Timestamps are integers and arrive in nondecreasing order

Function Signature

def unique_users_in_buffers(events, k):

Formal Specification

Input: events, a list of pairs [userId, time], and positive integer k.
userId is a string, and time is an integer. Events are provided in nondecreasing timestamp order, but timestamps may repeat.
Output: A list of lists. The element at index i contains the distinct user IDs in the buffer after processing events[i], ordered by first appearance in that buffer.
The original input must not be modified.