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 dequedeque 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 kk 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

Pattern 1 — a queue as a time window

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)

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 pingping — each timestamp is appended once and popped at most once, so nn pings do $O(n)$ total work. A single pingping can be $O(n)$ if a long-idle period expires many entries at once. Space $O(w)$, where ww is the number of pings inside the window.

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 kk 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.

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]

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]

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.

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

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

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

The variant map

Practice — real LeetCode problems

LC 933 — Number of Recent Calls · Easy

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

Constraints. 1 <= t <= 10^91 <= t <= 10^9, each pingping uses a strictly larger tt, up to 10^410^4 calls.

Examples. ping(1)ping(1) gives 11, ping(100)ping(100) gives 22, ping(3001)ping(3001) gives 33, ping(3002)ping(3002) gives 33 (the call at t = 1t = 1 has just expired)

LC 1352 — Product of the Last K Numbers · Medium

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

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

Examples. After adding 3, 0, 2, 5, 43, 0, 2, 5, 4: getProduct(2)getProduct(2) gives 2020, getProduct(3)getProduct(3) gives 4040, getProduct(4)getProduct(4) gives 00 (the window reaches the zero). Then add(8)add(8) and getProduct(2)getProduct(2) gives 3232.

LC 355 — Design Twitter · Medium

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

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

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

LeetCode problem set

Interview follow-ups

Edge-case checklist

• Window boundary exactly at the limit — ping(3001)ping(3001) after ping(1)ping(1) counts 11; inclusive means <<, not <=<=.
• A long gap between events — one pingping expires many entries; still $O(1)$ amortised.
• First operation — the queue has exactly the just-added element, so q[0]q[0] is safe.
• Zero added (LC 1352) — resets the history; getProductgetProduct spanning it must return 00.
• kk exactly at the reset boundary — k >= len(prefix)k >= len(prefix) returns 00.
• 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 discarddiscard.
• More than 10 tweets from one user — only the newest 10 appear, newest first.

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 kk items per source can reach the global top kk.
• Use a global counter as a clock for a free total ordering.
• Prefer discarddiscard over removeremove 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.