Class-Design Coding Rounds

Some coding rounds aren't puzzles. You're asked to build a small stateful class, such as a rate limiter, a leaderboard or a session tracker, and then the interviewer pushes on it: "what if there are millions of users?", "what if two requests arrive at once?". These rounds sit between DSA and low-level design. They reward picking the right data structures, explaining trade-offs, and proactively raising memory, concurrency and scale before you're asked.

The flow#

Work through these five steps in order, out loud.

Understand the requirements. Write down what's given and what's asked. Treat the interviewer as a client with a problem and yourself as the consultant.
Brainstorm and call out assumptions. Do you need to keep history, or can you decide on the fly? Is approximate accuracy acceptable?
List edge cases. Missing fields, unexpected types, empty data, out-of-order timestamps.
Discuss trade-offs. Which data structure and why, usually speed versus memory. There's no perfect answer, only trade-offs.
- "A deque of timestamps is exact but $O(n)$ memory; a token bucket is $O(1)$ memory but approximate."
- "In this exercise SortedList is fine; without that library, a heap with lazy deletion does the job."
Address scale in plain English. You don't need a full system design. Explain that in-process state (self.counts) won't survive multiple servers and would move to a shared store like Redis, and that simultaneous requests need atomic operations or locks.

Choosing data structures#

Most class-design rounds come down to picking the right container for each piece of state.

Data structure	Typical use	Time	Why it fits
Hash map (`dict`)	ID → object, counters	$O(1)$	Instant lookup of any entity
Hash set	Uniqueness: blocked users, tags	$O(1)$	Duplicates disappear for free
Deque	Time windows, undo history	$O(1)$ at both ends	Cheaply drop the oldest entries
List (dynamic array)	Ordered history, index jumps	$O(1)$ append and index	Jump to any position by index
`bisect` on a sorted list	Range queries, "closest value"	$O(\log n)$ search	Fast search without a database
Heap	Top k, next deadline	$O(\log n)$ push/pop	Ranks without fully sorting
Sorted set (`SortedList`, Redis ZSET)	Leaderboards with changing scores	$O(\log n)$	Always sorted, supports removal
Trie	Prefix matching, autocomplete	$O(\text{word length})$	Shares common prefixes

A quick way to choose for "track and rank" problems:

Question	If yes	If no
Does order matter?	Go to the next question	Hash map / hash set
Ordered by time (oldest first)?	Deque	Ordered by value: see next row
Ordered by value or rank?	Heap or sorted set	Hash map
Does data expire?	Track the oldest with a deque or heap and prune on each call	Keep it
Can scores tie?	Use tuple keys, e.g. `(-score, first_seen, user_id)`	Plain values

A deque is ideal for removing old data; a heap is ideal for ranking what remains. Many problems need both.

Combining structures#

Scenario	Combination
Frequency counter	`dict[entity] -> count`
Top k in the last 60 minutes	Deque (expiry) + dict (counts) + min-heap of size k (ranking)
Fast lookup + ordered access (LRU cache)	Dict + doubly linked list (or `OrderedDict`)
Prefix matching	Trie
Search by several fields	One dict per field (secondary indexes), updated together
Out-of-order events	Priority queue keyed by timestamp instead of a deque

The three things to raise unprompted#

Memory: does it grow forever?#

For every dict or list, ask when does data get deleted? A tracker keyed by user ID that never prunes is a memory leak.
Store timestamps (e.g. a deque of (timestamp, ...)) so you can evict old entries.
Mention lazy deletion (clean up when you next touch the data) or TTLs (let entries expire).

Speed: what happens when $n$ is a million?#

Is each operation $O(1)$ , $O(\log n)$ or $O(n)$ ? Will the call time out at scale?
Use a dict for lookups instead of scanning a list.
Keep a heap or sorted set so "top k" doesn't sort everything on every request.

Correctness under concurrency#

"What if two requests hit at the same moment?" In a multithreaded server, wrap read-modify-write logic in a lock: with self.lock: ....
Across servers, local locks don't help: use atomic operations in a shared store (e.g. Redis INCR/DECR) or a distributed lock.
When you finish, don't stop at "it works". Add: "To make this production-ready across servers, I'd move the counters to Redis and use atomic operations."

Trigger phrases and responses#

Interviewers signal the follow-up they want with certain phrases. Learn to recognise them:

The interviewer says...	Think	Reach for
"Millions of users"	Distributed state	Redis or a database instead of in-process dicts
"Memory is full"	Bounded state	Pruning, TTL, circular buffer, LRU eviction
"CPU is at 100%" / "too many writes"	Throughput	Batch writes through a buffer (flush every N events)
"Latency is too high"	Read path	Read-through cache (LRU) for hot data
"Top 10 items"	Ranking state	Heap + dict
"Last 5 minutes"	Time window	Deque of timestamps
"Concurrent calls"	Thread safety	Mutex lock, atomic counters
"Duplicate requests / data is wrong"	Integrity	Idempotency keys
"The server crashed"	Durability	Write-ahead log, persistence
"Read-heavy" vs "write-heavy"	Where to pay the cost	Precompute on write for read-heavy; keep writes cheap for write-heavy

Basic answer vs. stronger answer#

The same point can be made at different levels. Aim for the right-hand column.

Area	Basic answer	Stronger answer
Clarifying	"Is the input an integer?"	"How should out-of-order timestamps be handled?"
Speed	"It passed the tests."	"A heap keeps `get_top_k` at $O(k \log n)$ instead of a full sort."
Memory	"Python manages memory."	"Old entries are pruned on each call, so memory stays bounded."
Scale	"Use a bigger server."	"With many servers, the counters move to Redis with TTLs."
Concurrency	"The logic is simple."	"Updates run under a lock so counts can't race."
Edge cases	Waits for the interviewer	Handles `None`, empty windows and ties up front

Pacing a 45-minute round#

Split the time roughly like this, so scale gets discussed before the clock runs out:

First ~5 minutes, clarify. Accuracy vs. performance ("is a small error margin acceptable?"), scale ("100 requests a second or millions?"), and failure mode ("if unsure, block or allow?").
Next 10–15 minutes, core logic. Code the in-memory version with clear names (is_within_window, not x) and narrate: "Using a deque here so expired timestamps pop from the front in $O(1)$ ."
Last ~10 minutes, scale. If the interviewer doesn't raise it, you do: memory growth (pruning, circular buffer), races (locks), and multiple servers (shared store with TTLs).

Rapid-fire scenarios#

Practise with these common follow-ups and the answers interviewers look for.

Scenario	Follow-up	Answer
Session tracker in a dict; 10 million one-time users	"Memory is at 95%. How do you stop the crash?"	Evict with an LRU cache, or store sessions in Redis with a TTL so stale ones delete themselves
10 items left, 100 buyers click at once	"How do you avoid selling 15?"	It's a race: a lock on one server, or an atomic Redis `DECR` that refuses to go below zero across servers
Browser history as a linked list; jump back 400,000 pages	"The UI freezes. How do you make it instant?"	Store pages in a dynamic array and keep a current index: `current = max(0, current - steps)` is $O(1)$
Rate limiter of 100/min copied onto 50 servers	"A client sends 90/min to each server. Why isn't it blocked?"	State is siloed per server; move the counter to a shared store so all servers check one source of truth
"Top 10 trending topics" at 100,000 events/s	"Sorting on every event is killing the CPU."	Keep counts in a dict and a min-heap of size 10; replace the heap's minimum only when a count beats it, $O(\log 10)$ per update

Worked example: a toxic-comment monitor#

Problem. Build a SafetyMonitor:

record_comment(user_id, is_toxic, timestamp) is called for every comment. Toxic comments add to the user's score.
get_top_offenders(k) returns the k users with the highest score in the last 60 minutes. Ties go to the user who reached that score first.
A toxic comment older than 3,600 seconds expires and stops counting.

1. Clarify.

Is the score a simple count, or are some comments weighted more? (Assume a count.)
How often is get_top_offenders called compared with record_comment? That decides whether to keep rankings sorted at all times or compute them on demand.
How big is k: top 5 or top 50,000?

2. Data structures. Two problems at once: expiry and ranking.

Expiry: a deque of (timestamp, user_id) for toxic comments only. Expired ones pop from the front.
Scores: a dict user_id -> count.
Tie-breaker: a dict user_id -> time they reached their current score.
Ranking: a heap or sorted set, so you don't sort everyone on every call.

3. The edge case that catches people. A user who was toxic 61 minutes ago and has been silent since should have score 0. If you only update scores inside record_comment, that user stays at the top forever. Fix: evict expired entries at the start of both methods.

4. Trade-offs.

Sorted set: fast reads, but every score change is a remove + reinsert at $O(\log n)$ .
Size-k min-heap built on demand: cheaper writes; better when comments are frequent and rankings are requested rarely.

5. Scale. A Python deque holding every toxic comment will eventually exhaust memory on one machine. Move the event stream to a TTL-based store (e.g. Redis sorted sets keyed by timestamp) or a time-series database, keeping the same tie-break rule.

Key takeaways#

Treat the interviewer as a client: clarify accuracy, scale and failure behaviour first.
Choose structures by trade-off and say it out loud: deque for expiry, heap for ranking, dict for lookup.
Always ask when data gets deleted; unbounded dicts are memory leaks.
Raise concurrency (locks, atomic ops) and multi-server state (shared store, TTLs) before you're asked.
Evict expired data in every method that reads it, not just the one that writes.