L63 · Senior-Flavour Coding

Series: LeetCode — From Basics to Interview-Ready · Session 63 / 65 · Phase 4 · Interview simulation

Why this session exists

Senior loops blend coding and design, and the blend catches people who prepared for both separately. The question looks like a coding problem — implement this class, these methods, here are the constraints — but the grading is partly on things a pure algorithm answer never addresses. What happens under concurrency. What happens when memory fills. What the API should be. Why you chose this structure over the obvious alternative.

The good news is that these problems are almost never algorithmically hard. Design Hit Counter is a queue. LRU Cache is a hash map plus a doubly linked list. Logger Rate Limiter is a hash map. Circular queue is an array plus modular arithmetic. Every one of them is a composition of primitives you have owned since Phase 1.

The skill is therefore not "learn new data structures". It is composing known primitives to satisfy an operational requirement, and narrating the requirements you are trading against. A candidate who implements LRU correctly and says nothing scores meaningfully below one who implements it correctly and mentions that the doubly linked list is what makes eviction O(1), that a real cache would need locking around both structures, and that TTL-based expiry would need a different structure entirely.

Blank-file warm-up

Five minutes. Write the LRU cache skeleton from memory — the hash map plus doubly linked list, with get and put both O(1).

This is the canonical senior-flavour problem and the one most likely to appear. What to check: did you use a dummy head and a dummy tail? Almost every bug in this structure comes from special-casing the ends. Two sentinel nodes eliminate the special cases entirely and the code gets shorter, not longer.

Pattern anatomy

The shape: a class with a small API, an operational constraint that rules out the obvious implementation, and a required complexity per operation.

The invariant differs per problem but the method is constant: identify which operation the naive structure makes slow, then add exactly one auxiliary structure that makes it fast, and maintain both in step. Every problem in this family is "hash map for lookup, plus something else for ordering".

# THE COMPOSITION TABLE — memorise this, it covers most of the family.
#
#   need O(1) lookup by key              -> hash map
#   need O(1) removal from the middle    -> doubly linked list (node stored in the map)
#   need ordering by time of arrival     -> queue / deque
#   need ordering by priority or value   -> heap
#   need fixed capacity, no allocation   -> circular array + modular arithmetic
#   need "how many in the last N seconds" -> deque of timestamps, or bucketed counters
#   need distribution across N servers    -> consistent hashing (ring + sorted keys)
#
# LRU CACHE — the archetype. hash map + doubly linked list.

class Node:
    __slots__ = ("k", "v", "prev", "next")
    def __init__(self, k=0, v=0):
        self.k, self.v = k, v
        self.prev = self.next = None
 
class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}
        self.head = Node()          # dummy: most recently used side
        self.tail = Node()          # dummy: least recently used side
        self.head.next = self.tail
        self.tail.prev = self.head
 
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
 
    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_front(node)       # touching it makes it most-recent
        return node.v
 
    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.k]     # MUST delete from the map too, not just the list

The two dummy nodes are the whole trick. With them, _remove and _add_front are four lines each with no null checks. Without them, every method needs head-and-tail special cases and the bug rate roughly triples.

The del self.map[lru.k] line is why nodes store their key. Forgetting it produces a map that grows without bound while the list stays capped — a memory leak that passes every functional test.

The cue

You are in senior-flavour territory, rather than pure algorithms, when:

1. The problem is stated as a class with methods rather than a function. Design X, Implement Y with an API. The design framing is the tell.
2. A required complexity is stated per operation, usually O(1). That requirement is what rules out the naive structure and forces the composition.
3. The problem mentions capacity, expiry, or eviction. Bounded resources are an operational concern and they signal that resource behaviour is being graded.
4. The obvious implementation works but is too slow for one specific operation. That one operation tells you exactly which auxiliary structure to add.
5. The interviewer asks "what would you change in production?" — or you can reasonably anticipate that they will. Concurrency, persistence, distribution and monitoring are all fair game and mostly unprompted-bonus territory.

Tell 4 is the mechanical one. Ask which single operation is slow under the naive design, look it up in the composition table, add that structure. The design part is mostly this lookup done deliberately.

Guided solve

Design Hit Counter. Count hits received in the past five minutes. hit(timestamp) records a hit; getHits(timestamp) returns the count within the trailing 300 seconds. Timestamps arrive in non-decreasing order.

Clarify first, out loud. Does the granularity matter — is per-second enough, or do we need sub-second? Are timestamps guaranteed monotonic? What is the expected hit rate? These are not filler questions; the answers change the structure. Monotonicity in particular is what makes the simple solution correct.

Simplest correct approach. Keep a list of every timestamp, and on getHits count those within the window. Correct, and the memory grows without bound while the query is O(n). State it, state why it fails, move on.

The deque version. Since timestamps are monotonic, old entries can be evicted from the front. A deque of timestamps gives amortised O(1) hits and O(1) queries after eviction.

from collections import deque
 
class HitCounter:
    def __init__(self):
        self.q = deque()
 
    def hit(self, timestamp):
        self.q.append(timestamp)
 
    def getHits(self, timestamp):
        while self.q and self.q[0] <= timestamp - 300:
            self.q.popleft()
        return len(self.q)

Clean, and it is the right answer to the question as literally asked. But there is a follow-up the interviewer is almost certainly holding, and you should raise it before they do: what happens at very high hit rates? A million hits per second means a deque holding three hundred million timestamps. Memory dies.

The bucketed version. If per-second granularity is acceptable — and it usually is for a hit counter — use 300 fixed buckets and overwrite stale ones lazily.

class HitCounter:
    def __init__(self):
        self.times = [0] * 300
        self.counts = [0] * 300
 
    def hit(self, timestamp):
        i = timestamp % 300
        if self.times[i] != timestamp:
            self.times[i] = timestamp      # bucket is stale: reset it
            self.counts[i] = 1
        else:
            self.counts[i] += 1
 
    def getHits(self, timestamp):
        return sum(c for t, c in zip(self.times, self.counts)
                   if timestamp - t < 300)

Constant memory regardless of hit rate. O(300) query, which is O(1) with respect to input size. The tradeoff is that granularity is now fixed at one second and cannot be changed without resizing.

Raising and resolving that follow-up unprompted is the whole difference between a mid-level answer and a senior one. The algorithm did not get harder; the operational reasoning appeared.

The concurrency note. Say this even if not asked: in a real service, hit is called from many threads, so both versions need synchronisation. The bucketed version can use per-bucket atomics or a striped lock, which scales better than a single lock around a shared deque. One sentence, and it signals production experience.

Solo timed

Fifteen minutes each.

• Logger Rate Limiter — print a message at most once per ten seconds. A hash map from message to last-printed time is the whole thing. The follow-up worth pre-empting: the map grows forever with distinct messages. What would you do about it?
• Design Circular Queue — a fixed-size array plus head and size. The classic pitfall is distinguishing full from empty when both leave the pointers equal; tracking size rather than only two pointers removes the ambiguity entirely.

If you finish early, sketch a consistent hashing ring: a sorted list of hash values with virtual nodes, plus a binary search to find the owning node. You will not be asked to implement it often, but being able to explain why it beats modulo hashing — only K/N keys move when a node joins or leaves, instead of nearly all of them — is worth having ready.

Common failure modes

Forgetting to delete from the map on eviction. The LRU leak. The list stays capped, the map grows forever, and every functional test passes. This is the most common LRU bug and it is a memory leak, which is exactly the kind of bug a senior round is designed to catch.

Special-casing head and tail instead of using sentinels. Triples the null checks and the bug rate. Two dummy nodes, always.

Full-versus-empty ambiguity in the circular queue. When head equals tail, the queue could be either. Track an explicit size, or deliberately waste one slot — but pick one and say which and why.

Answering only the algorithmic question. A correct LRU with no mention of thread safety, memory bounds, or the eviction-policy alternatives is a mid-level answer to a senior question. The code is table stakes here.

Missing the second-order requirement. Hit Counter's high-rate memory problem, Logger's unbounded key growth. These are the follow-ups, and raising them before being asked is where the differentiation happens.

Over-engineering the first pass. The mirror-image failure. Do not open with a distributed sharded implementation. Build the simple correct thing, then discuss what changes at scale. Sequence matters: correct first, then operational.

Complexity

LRU cache: get and put are both O(1) — a hash lookup plus a constant number of pointer updates. Space is O(capacity), and the doubly linked list is what makes the middle-removal O(1); a singly linked list forces an O(n) predecessor search and breaks the guarantee.

Hit Counter, deque version: hit is O(1). getHits is amortised O(1) because each timestamp is evicted at most once across the structure's lifetime, though a single call can be O(n) when a burst expires at once. Space is O(hits in window), which is unbounded in the hit rate.

Hit Counter, bucketed: hit is O(1), getHits is O(300) which is constant in the input. Space is O(300), fixed.

Circular queue: all operations O(1), space O(capacity), zero allocation after construction — which is the actual reason this structure exists in real systems.

Consistent hashing: lookup is O(log N) via binary search over the sorted ring. The property that matters is that adding or removing a node moves only about K/N keys, versus nearly all of them under modulo hashing.

Spaced queue

Design problems decay differently from algorithmic ones — the structure is easy to recall and the operational discussion is not. So the queue entry for these should record both:

• cold — implemented clean and raised at least one operational concern unprompted → 60 days
• warm — implemented clean, no operational discussion → 21 days
• hint — needed a nudge on the structure → 7 days
• failed — no working implementation → 2 days, then 7 days

LRU specifically should be at cold before any senior loop. It is the single most likely design-flavour question you will face, and "correct but silent" is not cold here.