Viewer Counter Class

01 · Question

A livestream dashboard needs to answer: how many arrivals of a given viewer type occurred within the last window seconds? Implement a ViewerCounter class. Each join call represents one arrival; no viewer IDs or departure events are provided, so this is an arrival count, not a count of unique viewers or people currently online.

Methods

ViewerCounter(window): create an empty counter with a positive integer window size, in seconds.
join(t, viewer_type): record one arrival at second t. It returns no count.
get_viewers(t, viewer_type): return the number of recorded arrivals of that type with timestamps in [t − window, t], including both endpoints. A query does not record an arrival or consume the counted arrivals.

The only types are guest, follower, and subscriber; count them separately. All timestamps are integers and never decrease across either method, including calls for different types. Repeated timestamps are allowed, and each arrival counts separately.

Example input: record arrivals

counter = ViewerCounter(window=10)
counter.join(2, "follower")
counter.join(2, "follower")
counter.join(2, "follower")
counter.join(3, "follower")
counter.join(3, "guest")

Next, call counter.get_viewers(t, viewer_type) in the following order:

t	Type	Window	Output
10	follower	[0, 10]	4
10	guest	[0, 10]	1
10	subscriber	[0, 10]	0
12	follower	[2, 12]	4
13	follower	[3, 13]	1
14	follower	[4, 14]	0

At t=12, all three arrivals at second 2 still count: they are exactly on the left boundary. At t=13, those three expire, leaving only the follower arrival at second 3. The guest never contributes to the follower count.

Follow-up: if many arrivals share a timestamp and type, compress their storage while keeping every query result unchanged.

02 · Analysis

1. Keep arrivals in time order. Use one FIFO queue per viewer type. join appends the timestamp to that type's queue. Because timestamps never decrease, the oldest arrivals are at the front, and expired arrivals always form a prefix.

2. Expire before counting. For a query at t, remove front timestamps while they are strictly less than t − window. Then return the queue length. Every remaining arrival is inside the requested interval: old entries were removed, and future entries cannot exist under the timestamp contract.

For the example's follower queue:

t = 12, cutoff = 2: [2, 2, 2, 3] -> count 4
t = 13, cutoff = 3:          [3] -> count 1

Using <= instead of < would incorrectly return 1 at t=12. Counting a query must not remove arrivals that are still valid; they may contribute to later queries too.

3. Compress repeated arrivals (follow-up). Store (timestamp, count) groups and a running total for each type:

[2, 2, 2, 3] -> [(2, 3), (3, 1)]
                 3 + 1 = 4 arrivals, not 2

On arrival, increment the last group's count if its timestamp matches; otherwise append a new group. Increment the total by one. When a group expires, subtract its count from the total. The second solution cleans all three types on every call, so even a type that is never queried releases expired groups.

Costs. In the basic version, join is O(1); a query removing r expired arrivals takes O(r+1). Each arrival is inserted and removed once, so calls are amortized O(1), but one query can do substantial cleanup. Space is O(E) for retained events; types never queried can retain their entire history.

In the grouped version, a call removing r groups takes O(r+1), still amortized O(1) because there are only three types and each group is removed once. After cleanup, space is O(G) for the timestamp/type groups still in the window. Queries return the stored total without summing all groups again.

03 · Solution

Reference solution

1. One FIFO queue per viewer type

1from collections import deque
2
3class ViewerCounter:
4    def __init__(self, window):
5        self.window = window
6        self.queues = {v: deque() for v in ("guest", "follower", "subscriber")}
7
8    def join(self, t, viewer_type):
9        self.queues[viewer_type].append(t)
10
11    def get_viewers(self, t, viewer_type):
12        queue = self.queues[viewer_type]
13        while queue and queue[0] < t - self.window:
14            queue.popleft()
15        return len(queue)

2. Follow-up: grouped timestamps and running totals

1from collections import deque
2
3class GroupedViewerCounter:
4    def __init__(self, window):
5        self.window = window
6        self.queues = {v: deque() for v in ("guest", "follower", "subscriber")}
7        self.totals = dict.fromkeys(self.queues, 0)
8
9    def _expire(self, t):
10        for viewer_type, queue in self.queues.items():
11            while queue and queue[0][0] < t - self.window:
12                _, count = queue.popleft()
13                self.totals[viewer_type] -= count
14
15    def join(self, t, viewer_type):
16        self._expire(t)
17        queue = self.queues[viewer_type]
18        if queue and queue[-1][0] == t:
19            queue[-1][1] += 1
20        else:
21            queue.append([t, 1])
22        self.totals[viewer_type] += 1
23
24    def get_viewers(self, t, viewer_type):
25        self._expire(t)
26        return self.totals[viewer_type]

Compress Array by K

Current URL