Design Trackers and Feeds

These are the design problems that feel closest to real systems work: rate limiters, hit counters, activity feeds. They are also where interviewers most often follow up with “and now make it work at scale”, so the reasoning matters as much as the code.

Two ideas do most of the work:

1. A queue is a time window. If events arrive in non-decreasing time order, a deque holding the events currently inside the window is enough — push the new one, drop the expired ones from the front.
2. Do not compute what you can maintain. A feed does not need every tweet sorted; it needs the newest ten. Bounding what you keep, and what you look at, is what keeps these designs fast.

What you’ll learn

• The sliding-window queue for time-bounded counting, and its amortised cost.
• Prefix products with a reset trick to handle zeros — and why division needs care.
• Bounded k-way merge for feeds: why only the last k items per source matter.
• How to answer the inevitable “how would this scale?” follow-up honestly.
• Three real LeetCode problems solved in the browser: 933, 1352, 355.

The cue

You are looking at a tracker or feed design when…

• Counting events within the last N seconds — 933, 362, 359.
• Rate limiting — allow an action only if it has not happened recently.
• A merged, ranked feed from multiple sources — 355.
• Running aggregates over a suffix of a stream — 1352, 346 moving average.
• The problem mentions timestamps that arrive in non-decreasing order — that guarantee is what makes a queue sufficient.

The timestamp guarantee is load-bearing

LC 933 and 362 both promise that calls arrive with non-decreasing timestamps. That is what makes a deque correct: expired events are always at the front, so you can drop them without searching.

If timestamps could arrive out of order, a queue no longer works — you would need a sorted structure (a heap, a SortedList, or a Fenwick tree over time buckets). Asking “are timestamps monotonic?” is a genuinely good clarifying question here, not a formality.

Pattern 1 — a queue as a time window

recent_counter.py

from collections import deque
 
 
class RecentCounter:
    def __init__(self):
        self.q = deque()
 
    def ping(self, t):
        self.q.append(t)
        while self.q[0] < t - 3000:      # window is (t - 3000, t] inclusive
            self.q.popleft()             # expired: drop from the FRONT
        return len(self.q)

Time $O(1)$ amortised per ping — each timestamp is appended once and popped at most once, so n pings do $O(n)$ total work. A single ping can be $O(n)$ if a long-idle period expires many entries at once. Space $O(w)$, where w is the number of pings inside the window.

Get the window boundary right

LC 933 counts pings in the inclusive range [t - 3000, t]. So an entry expires only when it is strictly less than t - 3000:

• while self.q[0] < t - 3000 — correct.
• while self.q[0] <= t - 3000 — wrong; it drops an entry exactly on the boundary.

The test case ping(3001) after ping(1) is the one that catches this: 1 is exactly 3001 - 3000, so it must still count, giving 3. Read the interval notation in the problem statement carefully — half of these problems use inclusive bounds and half do not.

No explicit removal of old data is needed beyond this, and the queue never grows unboundedly as long as the window is bounded — which is exactly why the design is memory-safe for a long-running process.

Pattern 2 — prefix products with a reset

LC 1352 needs the product of the last k numbers added. Prefix sums let you get a range sum by subtraction; prefix products let you get a range product by division — which works right up until someone adds a zero.

product_of_last_k.py

class ProductOfNumbers:
    def __init__(self):
        self.prefix = [1]              # prefix[i] = product of the last i values
 
    def add(self, num):
        if num == 0:
            self.prefix = [1]          # RESET: nothing before a zero is reachable
        else:
            self.prefix.append(self.prefix[-1] * num)
 
    def getProduct(self, k):
        if k >= len(self.prefix):
            return 0                   # the window reaches back past a zero
        return self.prefix[-1] // self.prefix[-1 - k]

Why resetting on zero is cleaner than handling zero

Once a zero has been added, any window containing it has product zero. So rather than tracking where the zeros are, throw the history away: restart the prefix list.

Then the length of prefix tells you how far back you can see. If the requested k reaches at or beyond that boundary, a zero lies inside the window and the answer is 0. Otherwise plain division works, because every value in the remaining history is non-zero.

This also sidesteps division by zero entirely — there is never a zero in the prefix array to divide by. Using // is safe here because the division is guaranteed exact: prefix[-1] is a product that includes every factor in prefix[-1-k].

Visual intuition

A news feed is a bounded k-way merge: k followees, each with a time-ordered list, and only the newest few needed. A size-limited heap is what stops you merging everything:

heapYou never merge the whole feed — only the k newest surviveLC 355 · O(n log k)

as a tree

heap is empty

as an array — the real thing

k3heap size0/3

1import heapq2 3def k_largest(nums, k):4    heap = []                        # MIN-heap of the k largest so far5    for v in nums:6        heapq.heappush(heap, v)7        if len(heap) > k:8            heapq.heappop(heap)      # evict the smallest9    return heap[0]                   # kth largest

k3

setupCounter-intuitive setup: to find the k **largest** values, use a **min**-heap. The root is then the smallest of the k best seen so far, which makes it exactly the element to throw away when a better one arrives — and exactly the answer at the end.

Play‹›1/13⟲

Concatenating every followee's posts and sorting is O(N log N) in the total post count. Keeping a heap of size k means each post costs at most log k, and the structure never holds more than k items -- which matters when a user follows thousands of accounts but the page shows ten posts.

Pattern 3 — bounded k-way merge for feeds

A news feed must merge tweets from every followee in reverse-chronological order. Two observations keep it cheap:

• You only need the newest 10, so only the last 10 tweets per user can possibly qualify. Everything older is dominated.
• A global timestamp counter gives a total ordering for free — no clock needed, and no ties.

twitter_feed.py

from collections import defaultdict
import heapq
 
 
class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)      # user -> [(time, tweetId)]
        self.following = defaultdict(set)    # user -> set of followees
 
    def postTweet(self, userId, tweetId):
        self.tweets[userId].append((self.time, tweetId))
        self.time += 1                       # a monotonic global clock
 
    def getNewsFeed(self, userId):
        candidates = []
        for u in self.following[userId] | {userId}:   # a user sees their own
            candidates.extend(self.tweets[u][-10:])   # only the last 10 matter
        return [tid for _, tid in heapq.nlargest(10, candidates)]
 
    def follow(self, followerId, followeeId):
        if followerId != followeeId:         # never self-follow
            self.following[followerId].add(followeeId)
 
    def unfollow(self, followerId, followeeId):
        self.following[followerId].discard(followeeId)   # discard: no KeyError

getNewsFeed is $O(f \log f)$ where f is the number of followees, since it gathers at most 10f candidates and nlargest is $O(m \log 10)$ over them.

Three details this design gets right on purpose

Include the user themselves. A user sees their own tweets. Using self.following[userId] | {userId} handles it in one expression, and the set union means self-following cannot produce duplicates.

discard, not remove. Unfollowing someone you never followed must be a no-op, and set.remove raises KeyError. discard does not.

Slice [-10:], do not sort everything. Sorting every followee’s whole history is the difference between a fast solution and a timeout on the larger tests.

Dry run

The sliding time window, and the boundary that decides it

The LC 933 sequence ping(1), ping(100), ping(3001), ping(3002). Watch the cutoff column — everything strictly below it leaves the front of the queue.

Call	Cutoff t - 3000	Dropped	Queue after	Returns
ping(1)	-2999	—	[1]	1
ping(100)	-2900	—	[1, 100]	2
ping(3001)	1	—	[1, 100, 3001]	3
ping(3002)	2	[1]	[100, 3001, 3002]	3

Row 3 is the whole caution made concrete. The cutoff is exactly 1, and the oldest entry is exactly 1. Under < t - 3000 it stays, and the answer is 3. Run the same sequence with <=:

Call	Queue after	Returns
ping(1)	[1]	1
ping(100)	[1, 100]	2
ping(3001)	[100, 3001]	2
ping(3002)	[100, 3001, 3002]	3

One value differs, on one call, out of four. Rows 1, 2 and 4 agree. That is what a boundary bug looks like — not a crash and not a broadly wrong answer, but a single row that only the test case sitting exactly on the boundary can expose.

Note also that row 4 does the only $O(n)$ work in the trace: it drops one entry. Across the whole sequence, four appends and one pop — each timestamp enters once and leaves at most once, which is the amortised argument. A single ping after a long idle gap could drop thousands at once, so the per-call bound is $O(n)$ and only the total is linear.

Prefix products surviving a zero

add(3), add(0), add(2), add(5), add(4), then queries. The array length is doing double duty — it is both the prefix table and the “how far back can I see” marker.

Call	prefix	Reachable history	Returns
add(3)	[1, 3]	1	—
add(0)	[1]	0	—
add(2)	[1, 2]	1	—
add(5)	[1, 2, 10]	2	—
add(4)	[1, 2, 10, 40]	3	—
getProduct(2)	[1, 2, 10, 40]	3	40 // 2 = 20
getProduct(3)	[1, 2, 10, 40]	3	40 // 1 = 40
getProduct(4)	[1, 2, 10, 40]	3	0 — reaches past the zero
add(8)	[1, 2, 10, 40, 320]	4	—
getProduct(2)	[1, 2, 10, 40, 320]	4	320 // 10 = 32

The add(0) row is the design. Everything before the zero is discarded, not annotated — because any window reaching a zero has product zero, so there is nothing to remember about it. What remains is a table of strictly non-zero values, which means the division in getProduct can never divide by zero and never has to check for one.

getProduct(4) then costs nothing to answer: k = 4 is not less than len(prefix) = 4, so the window reaches at or past the reset point and the answer is 0 immediately. The list length carries the zero’s position; no separate index is needed.

The // is exact division, not truncation. prefix[-1] contains every factor of prefix[-1-k] by construction, so the quotient is always a whole number — 40 // 2 is 20 with no remainder, because 40 = 2 x 4 x 5.

The feed, pull model

postTweet(1, 5), getNewsFeed(1), follow(1, 2), postTweet(2, 6), getNewsFeed(1), unfollow(1, 2), getNewsFeed(1).

Call	tweets	following[1]	Returns
postTweet(1, 5)	{1: [(0, 5)]}	{}	—
getNewsFeed(1)	—	{}	[5]
follow(1, 2)	—	{2}	—
postTweet(2, 6)	{1: [(0,5)], 2: [(1,6)]}	{2}	—
getNewsFeed(1)	—	{2}	[6, 5]
unfollow(1, 2)	—	{}	—
getNewsFeed(1)	—	{}	[5]

Row 2 is the detail people miss: user 1 follows nobody, yet the feed is [5]. A user sees their own tweets, which is what self.following[userId] | {userId} buys — and because it is a set union, a stray self-follow cannot double a tweet.

The global counter is why row 5 orders correctly without a clock: tweet 5 has stamp 0 and tweet 6 has stamp 1, so nlargest puts 6 first. Real timestamps would risk ties; a monotonic integer cannot.

Row 6 is discard, not remove — and unfollow(1, 9), on someone never followed, is a silent no-op rather than a KeyError.

The bucketed hit counter (LC 362)

300 fixed slots, slot t % 300 holding (timestamp, count). Hits at t = 1, 2, 3, then a hit at t = 300:

Query	Result	Why
getHits(4)	3	slots for 1, 2, 3 are all within 300 seconds
getHits(300)	3	still inside the window — 300 - 1 = 299 < 300
hit(300), then getHits(300)	4	300 % 300 = 0, a different slot from 1 % 300 = 1, so nothing is overwritten
getHits(301)	3	301 - 1 = 300, so the t = 1 hit has just aged out

Memory here is 300 pairs, forever, whether the counter sees four hits or four billion. That fixed bound is the entire reason the bucketed version exists, and it is the answer to the standard follow-up “what if there are a huge number of hits per second?”.

Complexity

Design	Cost	Space
Windowed counter (queue)	$O(1)$ amortised	$O(\text{events in window})$
Prefix products	$O(1)$ per add and query	$O(n)$ since the last zero
Feed (pull model)	$O(f \log f)$ per read	$O(\text{tweets})$
Feed (push model)	$O(f)$ per write, $O(1)$ per read	$O(f \times \text{feed size})$

The variant map

Variant	The structure	Canonical problem
Count events in a window	deque of timestamps	933 · 362
Rate limit per key	Dict of key to last-allowed timestamp	359 (Premium)
Running average of last k	deque with maxlen + a running sum	346
Product of last k	Prefix products with a zero reset	1352
Merged ranked feed	Bounded k-way merge with a heap	355
Top-k over a stream	A size-k heap; see Top K	703

LC 362 — when the window is huge, bucket it

Design Hit Counter counts hits in the last 300 seconds. A deque of individual timestamps works, but if there are millions of hits per second it holds millions of entries.

The bucketed alternative uses a fixed array of 300 slots: slot t % 300 holds a (timestamp, count) pair. On a hit, if the slot’s stored timestamp is stale, overwrite it and reset the count; otherwise increment. A query sums the slots whose timestamps are within the window.

That is $O(300) = O(1)$ per operation and $O(1)$ space regardless of traffic. It is the standard answer when the follow-up is “what if there are a huge number of hits?”, and it is how real rate limiters are built.

Practice — real LeetCode problems

LC 933 — Number of Recent Calls · Easy

Problem. Implement RecentCounter with a single method ping(t) that records a call at time t and returns the number of calls that happened in the inclusive range [t - 3000, t]. Calls arrive with strictly increasing values of t.

Constraints. 1 <= t <= 10^9, each ping uses a strictly larger t, up to 10^4 calls.

Examples. ping(1) gives 1, ping(100) gives 2, ping(3001) gives 3, ping(3002) gives 3 (the call at t = 1 has just expired)

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Because timestamps only increase, everything that has expired sits at the front of the queue. So each ping appends once and drops a prefix.

Time $O(1)$ amortised — each timestamp is added once and removed at most once, so n pings cost $O(n)$ total. Space $O(w)$ for the pings inside the window.

The boundary is the whole difficulty. ping(3001) returns 3 because the call at t = 1 is exactly 3001 - 3000 and the range is inclusive. Then ping(3002) returns 3 again: the call at 1 finally expires (it is now strictly below 3002 - 3000 = 2), but the new call replaces it. Using <= instead of < returns 2 and 3 — wrong on the first, and it is precisely the case the examples are chosen to expose.

Note that self.q[0] is safe without an emptiness check, because t was just appended — the queue always has at least one element when the loop runs.

Follow-ups you should expect:

• “What if there are millions of pings per second (LC 362)?” Bucket by second: a fixed 300- or 3000-slot array of (timestamp, count) pairs. $O(1)$ space regardless of traffic.
• “What if timestamps could arrive out of order?” The queue breaks; use a sorted structure or a Fenwick tree over time buckets, and say so — this is the assumption the design rests on.
• “Support querying at an arbitrary past time?” Keep the full history plus a prefix count, then binary search.
• “A rate limiter that allows at most N per window?” Same queue, and reject when len(q) > N after appending.

LC 1352 — Product of the Last K Numbers · Medium

Problem. Implement add(num) and getProduct(k), returning the product of the last k numbers added. It is guaranteed that k never exceeds the count of numbers added.

Constraints. 0 <= num <= 100, 1 <= k <= 4 * 10^4, up to 4 * 10^4 calls, and the answer fits in a 32-bit integer.

Examples. After adding 3, 0, 2, 5, 4: getProduct(2) gives 20, getProduct(3) gives 40, getProduct(4) gives 0 (the window reaches the zero). Then add(8) and getProduct(2) gives 32.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Prefix products give a range product by division, the same way prefix sums give a range sum by subtraction. Zeros are the only complication, and resetting handles them completely.

Time $O(1)$ for both operations. Space $O(n)$ since the last zero.

Trace the example. After 3, 0, 2, 5, 4, the zero reset the list, so prefix = [1, 2, 10, 40] — covering only 2, 5, 4.

• getProduct(2) gives 40 // 2 = 20. ✅
• getProduct(3) gives 40 // 1 = 40. ✅
• getProduct(4): 4 >= len(prefix) == 4, so the window reaches back past the reset boundary and the answer is 0. ✅

That last case is the whole design. len(prefix) is exactly “how many values I can still see”, so one comparison detects a zero in the window without storing any zero positions.

Using // is safe because the division is exact — prefix[-1] contains every factor of prefix[-1-k] by construction. Using / would return a float and lose precision on large products, so integer division is the correct choice, not merely a stylistic one.

Follow-ups you should expect: “Why not keep a list and multiply the last k on demand?” — that is $O(k)$ per query and TLEs at $4 \times 10^4$ queries. “Support removal from the front?” — prefix products no longer suffice; you would need a Fenwick tree over logs, or a two-stack running-product trick. “Negative numbers?” — division still works and the sign takes care of itself; only zero is special. “Products overflowing?” — a non-issue in Python, but in a fixed-width language you would track logarithms or use modular arithmetic.

LC 355 — Design Twitter · Medium

Problem. Implement a simplified Twitter with postTweet(userId, tweetId), getNewsFeed(userId) returning the 10 most recent tweet ids from the user and the people they follow (most recent first), follow(followerId, followeeId) and unfollow(followerId, followeeId).

Constraints. 1 <= userId, tweetId <= 500, up to 3 * 10^4 calls.

Examples. postTweet(1, 5), getNewsFeed(1) gives [5], follow(1, 2), postTweet(2, 6), getNewsFeed(1) gives [6, 5], unfollow(1, 2), getNewsFeed(1) gives [5]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

This is a pull model: tweets are stored per author, and the feed is assembled on read by merging the newest tweets from the people you follow.

Time postTweet, follow and unfollow are $O(1)$. getNewsFeed is $O(f \log f)$ for f followees, gathering at most 10f candidates. Space $O(\text{tweets} + \text{follow edges})$.

Four decisions worth stating:

• A global counter as the clock. It gives every tweet a unique, increasing timestamp with no ties and no reliance on wall-clock time. Comparing (time, tweetId) tuples then sorts correctly by recency.
• Only the last 10 per user. An 11th-newest tweet from one author cannot be in the global newest 10, since the 10 newer ones from that same author all beat it. Slicing turns an unbounded merge into a bounded one — the key optimisation.
• Include the user themselves. The set union | {userId} does it in one expression and makes a self-follow harmless.
• discard over remove. The test unfollows user 99, never followed; remove would raise KeyError.

The last test case posts 12 tweets from one user and expects [12..3] — verifying both the 10-item cap and the newest-first ordering.

Follow-ups you should expect:

• “How would this scale? Pull or push?” The real discussion. Pull (this design) makes writes cheap and reads expensive — bad for users following thousands of accounts. Push (fan-out on write) precomputes each user’s feed so reads are $O(1)$, but a celebrity with millions of followers makes a single post enormously expensive. Production systems do both: push for ordinary users, pull for high-follower accounts merged in at read time. Being able to name that hybrid is what the follow-up is fishing for.
• “Deleting tweets?” Tombstones, or filter at read time.
• “Feed ranked by relevance rather than time?” The heap key becomes a score, and the “only last 10” pruning is no longer valid, since an older tweet could outrank newer ones.
• “Use a k-way merge instead of nlargest?” With each user’s tweets already sorted, a heap of iterators gives $O(10 \log f)$ — see K-way Merge.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 359’s subtlety — a dict can leak

Logger Rate Limiter allows a message only once every 10 seconds. The obvious design is a dict from message to its last-allowed timestamp: $O(1)$ per call.

But that dict grows forever — every distinct message ever seen stays in memory. For an interview answer it is fine; if the follow-up is “this runs for months”, you need periodic cleanup, or a queue of (timestamp, message) pairs alongside a set so expired entries can be evicted, or an LRU/TTL cache as in Design LRU and LFU Caches.

Spotting the unbounded-growth problem unprompted is worth more than the $O(1)$ solution itself.

8 problems

4 easy4 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○346Moving Average from Data Streampremiumeasy`deque(maxlen=k)` plus a running sum
• ○359Logger Rate LimiterpremiumeasyDict of message to next-allowed timestamp
• ○703Kth Largest Element in a StreameasyA size-`k` min-heap; the root is the answerNeetCode 150
• ○933Number of Recent CallseasyA `deque` as a time window; the boundary is inclusive
• ○355Design TwittermediumBounded k-way merge; global counter as a clockNeetCode 150
• ○362Design Hit CounterpremiummediumBucket by second for $O(1)$ space under heavy traffic
• ○981Time Based Key-Value StoremediumNeetCode 150
• ○1352Product of the Last K NumbersmediumPrefix products, reset on zero

Interview follow-ups

They ask	What they’re checking	The answer
“Are timestamps monotonic?”	Whether you ask it	The queue design depends on it; out-of-order arrivals need a sorted structure or time buckets
“Amortised or worst case?”	Precision	The windowed counter is $O(1)$ amortised; one ping after a long idle gap can expire many entries
“Millions of events per second?”	Scaling instinct	Bucket by time unit — a fixed array of (timestamp, count) slots, $O(1)$ space regardless of volume
“Pull or push for the feed?”	Systems thinking	Pull = cheap writes, costly reads; push = the reverse and bad for celebrities; production hybridises the two
“Why only the last 10 tweets per user?”	The key optimisation	An 11th-newest tweet from one author is beaten by that author’s own 10 newer ones
“Does your dict grow forever?”	Production awareness	Yes for the naive rate limiter — add TTL eviction or a companion queue
“Why integer division?”	Care	The division is exact by construction; float division loses precision on large products

Edge-case checklist

• Window boundary exactly at the limit — ping(3001) after ping(1) counts 1; inclusive means <, not <=.
• A long gap between events — one ping expires many entries; still $O(1)$ amortised.
• First operation — the queue has exactly the just-added element, so q[0] is safe.
• Zero added (LC 1352) — resets the history; getProduct spanning it must return 0.
• k exactly at the reset boundary — k >= len(prefix) returns 0.
• No zeros ever — the plain prefix-product path.
• Empty feed — a user with no tweets and no followees returns [].
• Self-follow (LC 355) — must not duplicate the user’s own tweets.
• Unfollow someone never followed — must not raise; use discard.
• More than 10 tweets from one user — only the newest 10 appear, newest first.

Self-check

pch.quizTag pch.quizDefaultTitle

1. LC 933 counts pings in the inclusive range [t - 3000, t]. Which expiry condition is correct?

   A `while q[0] <= t - 3000: q.popleft()` B `while q[0] < t - 3000: q.popleft()` C Either -- the boundary case cannot occur in practice D Neither; the window must be rebuilt from scratch on each ping
   pch.quizShowAnswer

   B — `while q[0] < t - 3000: q.popleft()` — An entry expires only when it is strictly below the cutoff, because the cutoff itself is inside the window. The sequence ping(1), ping(100), ping(3001) is the discriminator: the cutoff is exactly 1 and the oldest entry is exactly 1, so the correct version returns 3 and the `<=` version returns 2. Every other call in the trace agrees, which is why this needs the boundary test case specifically.

2. The windowed counter is described as O(1) amortised. What is a single `ping` in the worst case?

   A O(1) -- the deque pops in constant time B O(n), when a long idle gap means one ping expires many entries at once C O(log n), because the deque is kept sorted D O(w) always, where w is the window width in seconds
   pch.quizShowAnswer

   B — O(n), when a long idle gap means one ping expires many entries at once — One ping can drain the whole queue. What is bounded is the total: each timestamp is appended exactly once and popped at most once, so n pings do O(n) work overall. Same accounting as the two-stack queue -- the append pre-pays for the eventual pop.

3. `ProductOfNumbers` resets `prefix = [1]` when a zero is added. Why is that better than recording where the zeros are?

   A It saves memory, but requires an extra index B Any window containing a zero has product zero, so nothing before the zero is ever needed -- and the remaining table has no zero to divide by C It is required because Python integers overflow D It makes `getProduct` O(log n) instead of O(n)
   pch.quizShowAnswer

   B — Any window containing a zero has product zero, so nothing before the zero is ever needed -- and the remaining table has no zero to divide by — Two problems solved by one line. The history before a zero is unreachable -- every window that spans it answers 0 -- so keeping it is pure bookkeeping. And because the surviving table is strictly non-zero, the division in `getProduct` can never divide by zero and never has to check. The list *length* then encodes how far back you can see, so no separate index is needed either.

4. After `add(3), add(0), add(2), add(5), add(4)`, what does `getProduct(4)` return and why?

   A 0, because k is not less than len(prefix) -- the window reaches at or past the reset B 120, the product of 2, 5, 4 and the earlier 3 C 40, the product of everything since the zero D It raises an IndexError
   pch.quizShowAnswer

   A — 0, because k is not less than len(prefix) -- the window reaches at or past the reset — `prefix` is [1, 2, 10, 40], length 4, so only three values are reachable. Asking for four means the window includes the zero, and the guard `k >= len(self.prefix)` returns 0 without touching the array. Note getProduct(3) does return 40 -- exactly three values reachable, exactly three requested. Off by one in that guard and you would read prefix[-4], the sentinel 1, on a window that should answer 0.

5. In the Twitter feed, `getNewsFeed(1)` returns [5] when user 1 follows nobody. Why?

   A A bug -- the feed should be empty B A user sees their own tweets; `self.following[userId] | {userId}` includes them, and the set union makes a self-follow harmless C Because defaultdict creates an empty follow set that includes the user D Because tweet 5 has timestamp 0, which sorts first
   pch.quizShowAnswer

   B — A user sees their own tweets; `self.following[userId] | {userId}` includes them, and the set union makes a self-follow harmless — The union is doing real work in one expression. Without it the user's own posts never appear -- a spec violation that passes any test where the user also follows someone. And because it is a set, a user who explicitly self-follows still gets each tweet once, rather than twice.

6. The follow-up is 'what if there are millions of hits per second?' for LC 362. What changes?

   A Compress the deque of timestamps B Use 300 fixed slots keyed by `t % 300`, each holding (timestamp, count) -- O(1) time and O(1) space regardless of traffic C Switch to a heap ordered by timestamp D Sample the hits and extrapolate
   pch.quizShowAnswer

   B — Use 300 fixed slots keyed by `t % 300`, each holding (timestamp, count) -- O(1) time and O(1) space regardless of traffic — A deque of individual timestamps is O(hits in window) space, which is unbounded when traffic is. Bucketing collapses each second into one slot: on a hit, overwrite the slot if its stored timestamp is stale, otherwise increment. Memory is 300 pairs whether the counter sees four hits or four billion. This is how real rate limiters are built, and naming that is worth credit.

Recall card

• A tracker is a window plus the right eviction rule. Identify what makes an entry stale, and the structure follows.
• deque of timestamps for “events in the last w”: append on arrival, popleft while the front is stale. $O(1)$ amortised, $O(n)$ on one call after an idle gap.
• Read the interval notation. Inclusive [t - w, t] means expire on strict <, not <=. A single boundary test case is the only thing that catches it.
• Prefix products with a zero reset — discard the history on 0, since every window spanning it answers 0 anyway. The surviving table is zero-free, so the division is always safe and always exact, and len(prefix) encodes how far back you can see.
• Feeds are a bounded k-way merge. Only the last 10 per followee can qualify; nlargest(10, …) over 10f candidates beats sorting everything.
• A monotonic global counter gives total ordering with no clock and no ties.
• discard, not remove — unfollowing a stranger must be a no-op.
• Bucket when the window is huge: t % w slots holding (timestamp, count) gives $O(1)$ time and $O(1)$ space at any traffic level. This is the answer to “what if there are millions of hits per second?”.

Recap

• A queue is a time window when timestamps arrive monotonically — expired events are always at the front. $O(1)$ amortised, and always confirm whether the interval is inclusive.
• If the event volume is huge, bucket by time unit for $O(1)$ space regardless of traffic.
• Prefix products give range products by division; reset on zero rather than tracking zeros, which also makes division-by-zero impossible. Use integer division — it is exact by construction.
• For feeds, bound what you merge: only the last k items per source can reach the global top k.
• Use a global counter as a clock for a free total ordering.
• Prefer discard over remove when an absent key is legal.
• The scaling follow-up is nearly always pull versus push, and the real answer is a hybrid. Watch for structures that grow without bound.

Next: Simulation and Stateful Iteration — problems where the algorithm is just “do exactly what the statement says”, carefully.