Senior-Flavour Coding

Review boundary and corrected contracts

These are practice protocols, not hiring rubrics. Times, score bands and review intervals are adjustable conventions; neither a difficulty label nor a score predicts an interview outcome. Record the input contract, evidence of correctness and what remains uncertain.

Learning objective: Compose a rate limiter, LRU cache and circular queue from known primitives; explain resource, expiry and concurrency tradeoffs.

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

Why this session exists

A class-based coding exercise can test both data-structure correctness and operational reasoning. Clarify the API, resource bound and per-operation cost before discussing distribution. These examples compose familiar primitives, but that does not establish the difficulty or grading of every senior interview.

A map supplies lookup; an ordering structure supplies the next eviction or expiration candidate. Explain why both are needed and what keeps them consistent. For a real service, also ask about synchronization, persistence, timestamp authority and overload behavior. A working in-memory model is not automatically a production-safe service. TTL can be added lazily to the same LRU structure; prompt expiry may need an additional index rather than an entirely different cache.

Blank-file warm-up

In five minutes, sketch LRU get and put, the key-to-node map and the recency chain. Use two sentinels for this implementation so every real node has neighbors. Check the invariant, not just whether the code resembles a template: exactly one list node per mapped key, with the most recently used node nearest the head. This is a useful practice choice, not evidence that LRU is the most frequently asked question.

Pattern anatomy

Choose the auxiliary structure for the operation that is slow, then specify the relation between structures. Not every design needs a map or exactly two structures: a circular queue only needs an array and indices.

# COMPOSITION TABLE — candidate mechanisms, subject to the API contract
# key lookup                  -> hash map (expected constant-time operations)
# remove a known middle node  -> doubly linked list
# ordered arrivals/expiry     -> deque, with a monotone time contract
# smallest priority           -> heap
# fixed storage slots         -> circular array and modular arithmetic
# trailing integer-second hits-> timestamp buckets, if that granularity is valid
# ring ownership              -> sorted token positions and successor search

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):
        if capacity < 0:
            raise ValueError("negative 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

This code takes a nonnegative integer capacity; zero capacity is supported and negative capacity raises ValueError. Keys are hashable. A missing key returns -1, so an application that permits -1 values needs a separate presence signal. Hashing/equality and stored values are assumed bounded-cost for the complexity model.

A hit unlinks and reinserts the same node at the front. Updating an existing key creates a replacement node after unlinking the old one; it must not increase the live list length. Overflow removes the tail's predecessor from both structures. Sentinels eliminate end special cases in these internal methods, not every null check in arbitrary linked-list code; _remove itself has two assignments and _add_front four.

Negative control: with capacity 1, put(1,10); put(2,20); get(1) must return -1. Deleting the eviction-map deletion line instead returns 10 from a stale node and can corrupt subsequent list state. This is a functional correctness bug as well as a retention bug, not a leak that passes every functional test. Traverse both directions after each operation and require that the list's node identities equal the map's values.

The cue

Look for a class API, an explicit per-operation bound, or a requirement involving capacity, expiry or eviction. None of these alone proves which structure to choose. Ask which operation a simple design makes expensive: a list lookup is linear; removing a known doubly linked node is constant pointer work; finding the earliest arbitrary expiry suggests a heap.

Then state the follow-up contract. “Thread-safe” needs an atomic operation boundary, not just a thread-safe container primitive. “Bounded memory” needs a bound on entries and, where relevant, value size. “Expiry” needs a clock, boundary convention and policy for late events. Keep speculative production extensions separate from the class you actually implemented.

Guided solve

Design Hit Counter. hit(t) records one hit; getHits(t) counts hits in (t-300, t]. All calls use nonnegative integer-second timestamps in nondecreasing order. Several hits may share a timestamp. A hit exactly 300 seconds old is excluded.

Clarify whether event time can arrive late, whether subsecond precision is needed, and how high the rate can get. Storing all timestamps and scanning them on every query is a correct reference under this contract, but its memory never shrinks and each query scans the full history.

Deque implementation. Expired timestamps form a prefix because calls are monotone:

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)

At query completion every retained timestamp is in the window. Each recorded hit is appended once and removed at most once, so H hits and Q queries take O(H + Q) deque work overall. One query may remove all retained hits. Importantly, hit does not evict: without queries the deque retains all hits since the last cleanup, including expired ones, not merely hits in the current window. Even with frequent queries, 1,000,000 hits/s × 300 s = 300,000,000 entries; feasibility depends on memory and representation.

Fixed second buckets. Keep one timestamp and count per residue modulo 300:

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)

At time t, a distinct older integer timestamp with the same residue is at least 300 seconds old. Resetting that slot therefore discards only expired hits. Within (t-300,t] no two different integer timestamps collide modulo 300. Monotonicity also means there are no future hits, which is why the query's one-sided age check is sufficient. Zero-filled slots have zero counts even when their timestamp passes the predicate.

There are 300 timestamp/count pairs regardless of rate; Python integers can still grow in bit length, so “constant memory” here means a fixed number of slots, not a strict byte bound for unbounded time/rate. Update is constant array work, query scans 300 buckets. For general window W seconds, these are O(1) and O(W), with O(W) slots. Exact subsecond windows require another representation or finer buckets, with boundary/rounding rules made explicit.

Concurrency is a separate design. In the bucketed version a timestamp reset and its count update must be coordinated; atomic increments alone do not make the pair safe. A query spanning buckets also needs a stated consistency model. Begin with a lock around an entire public operation if exact serialized behavior is required. Finer-grained locks or sharding need their own correctness argument and measured contention; no scalability improvement is guaranteed here.

Solo timed

Spend fifteen minutes on each drill, then use these reference contracts to review it.

Logger Rate Limiter. Print the same message at most once per ten seconds; denied attempts do not refresh its last-printed timestamp. Calls use monotone integer time. At exactly last + 10 the message is allowed. For example, attempts at 0, 9 and 10 return True, False, True.

class Logger:
    def __init__(self):
        self.last = {}
 
    def shouldPrintMessage(self, timestamp, message):
        if message in self.last and timestamp - self.last[message] < 10:
            return False
        self.last[message] = timestamp
        return True

The map grows with distinct messages. Cleanup may remove an entry when its last successful print is at least ten seconds old, since the next occurrence is then allowed. A full scan costs O(distinct messages); an expiry queue can amortize cleanup but must not delete a newer timestamp when an old record expires. Define a retention/overload policy before calling the service memory-bounded.

Circular Queue. A size counter distinguishes full and empty even when head and insertion position coincide. The next insertion slot is (head + size) % capacity; advancing head after removal reuses the vacated slot.

class CircularQueue:
    def __init__(self, capacity):
        if capacity < 0:
            raise ValueError("negative capacity")
        self.data = [None] * capacity
        self.head = 0
        self.size = 0
 
    def enqueue(self, value):
        if self.size == len(self.data):
            return False
        self.data[(self.head + self.size) % len(self.data)] = value
        self.size += 1
        return True
 
    def dequeue(self):
        if self.size == 0:
            raise IndexError("empty queue")
        value = self.data[self.head]
        self.data[self.head] = None
        self.head = (self.head + 1) % len(self.data)
        self.size -= 1
        return value

For capacity 2, enqueue A and B, reject C, dequeue A, enqueue C, then dequeue B and C. Capacity zero rejects every enqueue and raises on dequeue before any modulo-by-zero operation. Clearing a removed slot releases its reference. The array's slot count is fixed; Python object values and index arithmetic are not a zero-allocation systems guarantee.

Extension: consistent hashing. Sort T distinct token positions (including virtual nodes, with hash collisions resolved consistently); assign a key to the first clockwise token at or after its hash, wrapping at the end. Lookup is O(log T), not O(log physical servers) unless tokens per server are bounded. Inserting one token changes ownership only in the arc between its predecessor and itself; removing it transfers its arc to its successor. That is the deterministic locality property. Under balanced independent placement, adding one server to N equal servers moves an expected fraction about 1/(N+1) of K keys; removing one of N moves about 1/N. A poorly balanced ring can move much more. Virtual nodes improve distribution only with suitable placement; no fixed K/N guarantee holds for every ring. Unlike changing the modulus, unchanged arcs keep their owners.

Common failure modes

• LRU map/list divergence: stale evicted keys produce wrong hits; test capacity one and inspect node identities after every operation.
• Sentinel misuse: never remove a sentinel. Sentinels simplify endpoints but do not enforce correct links automatically.
• Queue full/empty ambiguity: choose size tracking or one unused slot. Say whether the stated capacity counts usable slots.
• Expiry ambiguity: test ages 299 and 300 for HitCounter, and 9 and 10 for Logger. Include repeated timestamps and a long idle gap.
• Ignoring retention: the deque cleans on queries only; the logger never cleans. Neither has a workload-independent byte bound.
• Over-engineering: satisfy the small API before adding services. Then identify the first requirement that invalidates your model.

The useful sequence is clarify, implement, establish invariants, test boundaries, and discuss resource/concurrency limits. This is not a formula for how reviewers award seniority. A map is like a filing cabinet and a recency list like an ordered conveyor: a key locates a node, and links relocate it without a search. The analogy stops at the actual maintained invariant.

Choose exact timestamps when the precision and retention budget allow them. Choose fixed buckets when the time granularity and window are fixed and a predictable slot count matters. There is no universal “1,000 hits/s” crossover: measure entry size, burst behavior, query frequency and acceptable precision. Expanding a deque's window after discarding old hits cannot recover the lost history; runtime adjustment needs a retained maximum horizon.

Complexity

LRU: expected O(1) lookup/update under a bounded-cost hash model plus constant pointer changes; O(C) entries for capacity C. Hash collisions, expensive keys and large values require qualifications. A singly linked list without predecessor bookkeeping needs a search for arbitrary removal; a doubly linked list is convenient, not the only possible LRU design. Python's OrderedDict supplies recency reordering too.

Deque counter: O(1) append, O(r+1) query when r timestamps expire, O(H+Q) aggregate work over H hits and Q queries. Space is retained hits since cleanup; after a query it equals hits in that query's window.

Bucket counter: O(1) update, O(W) query and O(W) slots for W integer seconds. W=300 is a fixed constant here; unbounded Python counters/timestamps have growing bit costs.

Logger: expected O(1) per attempt and O(M) map entries for M distinct messages without cleanup. Circular queue: O(1) operations on O(C) slots, with referenced values outside that slot bound. Ring: O(log T) lookup; inserting into a Python sorted list can still cost O(T) shifting.

Self-check (answer follows each question).

Q: Why use a doubly linked list rather than a singly linked one for this LRU?

A: The map yields the node, and its prev link permits arbitrary unlinking in constant pointer work. A plain singly linked list lacks that predecessor; alternative predecessor bookkeeping or OrderedDict can satisfy the goal too.

Q: What must the LRU node store besides its value, and why?

A: Its key, so eviction via the tail also deletes the corresponding map entry. Otherwise get can return an evicted value; this is directly observable, not merely a silent memory leak.

Q: Why do sentinel head and tail nodes simplify this implementation?

A: Each real node has a predecessor and successor, eliminating endpoint branches in these internal link operations. They do not prevent all bugs or establish a measured bug-rate reduction.

Q: When can the deque counter exceed its memory budget, and what is the alternative?

A: High rates create many entries, and hits without queries leave expired entries retained. A fixed array of timestamp/count buckets bounds slot count when integer-second precision is valid; it does not bound arbitrary integer/value bytes.

Q: Why is head == tail ambiguous in a circular queue, and how can it be resolved?

A: After a full wrap, both empty and full can share that equality. Track size explicitly, as above, or reserve one unused slot and advertise the reduced usable capacity.

Q: How can TTL expiry be added to LRU, and what happens to complexity?

A: Store expiry per node and lazily remove an expired node on access; expected O(1) map/list work remains and the capacity already bounds entries, though expired entries may occupy slots. Prompt reclamation is a different goal: a min-heap adds O(log E) insertion and O(log E) per removal for E heap records. Version checks reject stale records; compaction or indexed updates must bound E by O(C) before using O(log C), and a cleanup call may remove many records. A timing wheel has different resolution and amortization assumptions; it is not automatically O(log C). Define whether writes refresh TTL and which clock governs expiry.

Spaced queue

Log implementation and operational reasoning separately. Proposed intervals are cold 60 days (independent correct implementation plus a justified operational limit), warm 21 (implementation correct, discussion incomplete), hint 7 (assisted), failed 2 then 7 (no correct implementation). Adjust from delayed results; these are not measured decay laws.

For each revisit, test at least one structural invariant and boundary before calling the implementation correct. Key reminders: compose according to the API; sentinel placement simplifies this LRU but is not mandatory for every design; eviction must update both structures; bucket resets need a time contract; memory bounds and atomicity require explicit policies. A concrete limitation is useful explanation, not a guaranteed hiring signal.

Executable practice boundary

LRU, Logger and CircularQueue accept the stated integer capacities/timestamps without comprehensive type validation. Both HitCounter variants require nonnegative integer seconds, monotone across all calls, and the half-open window (t-300,t]. They are alternative classes with the same name: run their fences in separate namespaces. Out-of-order and subsecond inputs are outside the contract, not silently supported extensions.

All displayed examples are single-threaded in-memory models. The TTL and consistent-hashing extensions are derived design explanations, not service implementations. Tests extract the actual fenced classes, compare with independent list/history models and exercise deliberately broken mutants; they do not establish concurrency safety or maximum-load performance.

Corrective source notes

• Dunlosky and colleagues: Improving Students’ Learning With Effective Learning Techniques — publisher-hosted 2013 review summary, saved 2026-10-07 and re-read 2026-10-09. Supports the limited rationale for practice testing and distributed practice; not exact intervals, decay rates, coding-specific causal effects or hiring scores.
• Python 3.14 collections documentation — retrieved 2026-10-09. Documents approximately O(1) deque operations at either end and OrderedDict recency moves. This does not make a compound cache operation thread-safe.

Algorithmic arguments and arithmetic above are derived for the stated contracts. Finite executable checks, saved source passages and their limits are recorded in the review artifacts; they do not certify unexecuted service behavior or interview outcomes.