Design

Topic type: Data Structure — problems ask you to implement a data structure or system component with a specified operation API, evaluated on correctness and time complexity per operation.

Problem count: 200+ (full depth required)

---

1. Core Concepts

Amortized O(1) — an operation that occasionally costs O(n) but averages O(1) over a sequence of calls. Relevant for dynamic arrays, hash tables with rehashing, and move-to-front operations.

Composition — building a complex structure from two or more simpler primitives (e.g., dict + doubly linked list for LRU). The dict provides O(1) lookup; the linked list provides O(1) ordered eviction.

Sentinel node — a dummy head and/or tail node in a doubly linked list that eliminates all edge-case checks for empty list, first insertion, and last deletion. Every real node is between head and tail.

Lazy deletion — marking entries as deleted without physically removing them. Used when removal from a collection is expensive; actual cleanup happens on next access. Common in heaps augmented with a dict.

Frequency bucket — a list (or dict) indexed by access frequency, each containing the set of keys at that frequency. Core mechanism of LFU Cache.

Min-frequency pointer — in LFU Cache, a variable tracking the current minimum frequency bucket. Must be updated on every insert (reset to 1) and on every access (increment if bucket empties).

Doubly linked list as O(1) order tracker — an intrusive doubly linked list where nodes are stored by pointer in a hash map lets you move any node to head/tail in O(1) without searching.

Online algorithm — processes input one element at a time without seeing future data. Contrasted with offline algorithms that sort or pre-process the full input. Most "design" problems require online solutions.

Iterator protocol — an object exposing hasNext() / next() that advances state on each call. Key insight: hasNext() must not advance state; it is idempotent.

Intrusive list node — a node that contains application data directly rather than wrapping it. Avoids an extra allocation and lets the hash map store a direct pointer to the node.

---

2. Structural Invariants

---

3. Internal Representation

LRU Cache — dict mapping key → node reference (O(1) lookup) + doubly linked list maintaining recency order (O(1) move-to-front and tail eviction). The dict stores node pointers, not values, so moving a node in the list does not require updating the dict value.

LFU Cache — three structures: key_map: {key: (value, freq)}, freq_map: {freq: OrderedDict of keys} (ordered for O(1) oldest eviction within a frequency), and min_freq integer. Python's OrderedDict supports O(1) move-to-end and O(1) popitem(last=False).

MinStack — two lists: main stack and auxiliary min-stack. The min-stack records the running minimum at every depth. Push min-stack only when new value ≤ current min (or always, for simplicity). Pop both in sync.

RandomizedSet — list of active elements (for O(1) random access) + dict mapping value → index in list (for O(1) lookup and removal). Removal: swap target with last element, update dict, pop from list — O(1) without shifting.

TimeMap — dict mapping key → sorted list of (timestamp, value) pairs. Lookup uses binary search (bisect_right) for the largest timestamp ≤ query timestamp.

Custom iterator (flattening) — a stack of iterators. hasNext() advances the stack, unwrapping nested iterables until a scalar is found or the stack is empty. next() pops and returns the pre-fetched scalar.

Peeking iterator — wraps an existing iterator and maintains one element of lookahead. peek() returns the buffered element without advancing; next() returns it and refills the buffer.

Serialization — BFS level-order for trees (null markers for missing children); DFS pre-order with explicit null tokens also works. The format must be self-delimiting so deserialization can reconstruct structure without ambiguity.

---

4. Types / Variants

See heap-priority-queue.md for full coverage of heap operations. See doubly-linked-list.md for doubly linked list fundamentals.

---

5. Topic-Specific Operations

LRU Cache

get(key) — look up key in dict; if found, move node to head of list (most recent), return value; if not found, return -1. O(1).

put(key, value) — if key exists, update value and move to head; if not, create node, insert at head, add to dict. If capacity exceeded, evict tail node and remove from dict. O(1).

_move_to_head(node) — remove node from current position (update prev/next pointers of neighbours) then insert between sentinel head and head.next. O(1). This is the core operation — get it right once and reuse.

_evict_tail() — the node just before the sentinel tail is the LRU. Update its neighbours, remove from dict. O(1).

LFU Cache

get(key) — look up key; increment its frequency, move it to the new frequency bucket (add to end of freq_map[new_freq], remove from freq_map[old_freq]); if old_freq == min_freq and that bucket is now empty, increment min_freq. Return value. O(1).

put(key, value) — if key exists, update value and call get logic (frequency increment). If new key: if at capacity, evict the first (oldest) key in freq_map[min_freq]; insert new key into freq_map[1]; reset min_freq = 1. O(1).

MinStack

push(val) — append to main stack; append min(val, current_min) to min-stack. O(1).

pop() — pop from both stacks simultaneously. O(1).

getMin() — return top of min-stack without popping. O(1).

top() — return top of main stack without popping. O(1).

RandomizedSet

insert(val) — if val in dict, return False; else append val to list, store index in dict, return True. O(1).

remove(val) — if val not in dict, return False; else swap val with last element in list, update dict for the swapped element, pop list, delete val from dict, return True. O(1).

getRandom() — return list[random.randint(0, len-1)]. O(1) because list supports O(1) random access.

Iterator Operations

next() — return the buffered element (for peeking iterators) or advance and return. Must update internal state so hasNext() reflects the new position.

hasNext() — returns bool; must NOT advance state. Pre-fetch the next element into a buffer if the underlying source requires consuming to check. For flattening iterators, advance the stack until a scalar is available or the stack empties.

peek() — return buffered element without consuming it. Calls next() internally on the wrapped iterator if buffer is empty, stores result.

---

6. Key Algorithms

Doubly Linked List Node Move (LRU core)

Moving a node to head is the single most error-prone operation. The mechanism: disconnect the node (patch its neighbours), then insert between sentinel head and current first real node.

node.prev.next = node.next
node.next.prev = node.prev
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node

This is 6 lines but each line is load-bearing. Doing it wrong in any order causes pointer corruption. The sentinel head eliminates the if node.prev is None check.

Two-Heap Median Maintenance

Maintain a max-heap (lower half) and min-heap (upper half). After every insert, rebalance so sizes differ by at most 1. Median is the top of the larger heap (or average of both tops if equal size). Time O(log n) per insert, O(1) query.

heapq.heappush(self.lo, -num)   # max-heap via negation
heapq.heappush(self.hi, -heapq.heappop(self.lo))
if len(self.hi) > len(self.lo):
    heapq.heappush(self.lo, -heapq.heappop(self.hi))

Snap Array via Sparse Snapshots

Each cell stores a list of (snap_id, val) pairs, appended only on change. snap() increments a counter. get(index, snap_id) uses bisect_right on snap_ids to find the latest value at or before the requested snap_id. O(1) set, O(log s) get where s = number of snaps.

Frequency Bucket Eviction (LFU)

self.freq_map[old_f].pop(key)          # O(1) with OrderedDict
if not self.freq_map[old_f]:
    if self.min_freq == old_f: self.min_freq += 1
self.freq_map[old_f + 1][key] = val    # OrderedDict preserves insertion order

The OrderedDict's insertion order is the recency order within a frequency bucket. popitem(last=False) evicts the oldest. This entire pattern replaces a complex doubly linked list per frequency bucket.

Flattening Iterator via Stack

Push the outermost iterator onto a stack. In hasNext(), while the stack is non-empty and the top iterator is exhausted, pop it; if the next element of the top iterator is itself iterable, push its iterator. Stop when a scalar is at the front. Time: amortized O(1) per element.

Serialize / Deserialize Binary Tree

BFS with null markers: encode level-order into a comma-separated string, using "N" for null children. Decode by splitting, using a queue of parent nodes, and assigning left then right children from the token stream. O(n) time and space.

See binary-tree.md for traversal patterns used in serialization.

Consistent Hashing (Design problems involving distributed caches)

Map servers and keys to a ring via hash. Each key is served by the first server clockwise. Adding/removing a server only remaps keys in one arc. Key insight: virtual nodes (multiple positions per server) improve balance.

---

7. Advanced Techniques

Lazy Deletion in Priority Queue

Solves: Problems needing a priority queue where elements can be invalidated (e.g., Task Scheduler, Sliding Window Maximum, Top-K Frequent with updates).

Mechanism: Keep a dict of counts or a "tombstone" set. When popping from the heap, check if the element is still valid; if not, discard and pop again. Never physically remove from the heap.

Prefer over physical removal when: The heap is used in a hot loop and deletions are infrequent or can be deferred. Do not use if the heap grows unboundedly — tombstones accumulate O(n) memory.

Complexity: O(log n) per valid pop; O(k log n) total if k elements are lazily deleted before a valid one surfaces.

See heap-priority-queue.md for heap fundamentals.

Versioned / Persistent Data Structures

Solves: Problems that require querying historical states or rolling back operations (Snapshot Array, Persistent Segment Tree queries, offline undo).

Mechanism: On each "write," create a new version rather than mutating in place. Versions share structure (path copying in trees) so memory is O(log n) per update, not O(n).

Prefer over full copy when: Updates are sparse and the number of versions is large. Do not use for dense updates — path copying overhead exceeds full copy cost when nearly all nodes change.

Complexity: O(log n) per update and query for tree-based persistence; O(1) per update for sparse list (Snapshot Array style).

Augmented Ordered Structure (Order Statistics)

Solves: Problems requiring rank queries, predecessor/successor, and range counts alongside normal map operations (e.g., Count of Smaller Numbers After Self, Sliding Window Rank).

Mechanism: Maintain a sorted structure (balanced BST, skip list, or sorted list with bisect) alongside a frequency dict. In Python, SortedList from sortedcontainers provides O(log n) add/remove/rank in one structure.

Prefer over simple dict when: The problem asks for relative rank, kth smallest, or count of elements in a range. Overkill for pure frequency counting.

Complexity: O(log n) insert/delete/rank with SortedList; O(n log n) total for n operations.

Two-Stack / Two-Queue Simulation

Solves: Problems that require one abstract type's interface but only the other is available (Stack via Queues, Queue via Stacks), or amortized O(1) deque operations on a constrained interface.

Mechanism: Buffer one stack as the "input" side and flush to the "output" stack only when the output is empty. Each element crosses the boundary exactly once, giving amortized O(1) per operation.

Prefer over single-structure when: The problem explicitly restricts available primitives. In real code, use collections.deque instead.

Complexity: O(1) amortized per operation; O(n) worst case for a single pop that triggers a full transfer.

---

8. Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

9. Common Patterns

---

10. Edge Cases & Pitfalls

• Sentinel node setup omitted — forgetting to link sentinel head and sentinel tail to each other at init means the first real insertion has null prev/next and crashes. Always wire head.next = tail and tail.prev = head in __init__.

• Returning stale value on LFU get — after a get, the value dict must be updated with the new frequency before returning. A common bug: frequency updated in freq_map but the old freq left in key_map, so min_freq logic breaks on the next eviction.

• min_freq not reset on put — inserting a new key in LFU must unconditionally set min_freq = 1. If the previous min_freq was 3, the new key is in bucket 1 but min_freq still points to 3, so eviction picks the wrong key.

• Moving a node to head before disconnecting it — in LRU, connect the new neighbours first, then connect the node at the new position. Reversing the order overwrites pointers needed for the disconnect step.

• hasNext() advancing state — wrapping an iterator and calling __next__ inside hasNext() to check exhaustion consumes an element. Use a StopIteration-catching peek buffer instead.

• RandomizedSet index corruption on remove — after swapping the removed element with the last, you must update the dict entry for the swapped element to its new index. Forgetting this means its next remove() looks at the wrong list index.

• TimeMap insert out of order — binary search correctness requires timestamps to be non-decreasing per key. If the problem guarantees this (LeetCode 981 does), no check needed; if not, insertion must be sorted.

• Capacity = 0 in LRU/LFU — every put immediately evicts; get always returns -1. Common to forget this degenerate case in the init branch.

• Duplicate keys in put (LRU) — putting a key that already exists should update its value and move it to head, not add a second node. Missing the existence check adds duplicate nodes and corrupts eviction order.

• Median heap imbalance on empty stream — calling findMedian() before any addNum() call; guard with a size check or ensure the balancing invariant holds for size 0.

• Python heapq is min-heap — to simulate a max-heap for the lower half in median finding, negate all values on push and negate again on pop.

• OrderedDict popitem direction — popitem(last=False) removes the oldest (FIFO); popitem(last=True) removes the newest (LIFO). LFU needs oldest within a frequency bucket, so use last=False.

---

11. Implementation Notes

• Python's collections.OrderedDict supports O(1) move_to_end(key) and popitem(last=False) — use this to replace a per-frequency doubly linked list in LFU.
• heapq in Python is min-heap only; negate values for max-heap behaviour. Keep negation consistent across all push/pop sites or the heap ordering breaks silently.
• Python's default recursion limit is 1000; serialization/deserialization via recursive DFS on a tree of depth 500 will hit this. Use iterative BFS instead or sys.setrecursionlimit.
• random.choice(list) is O(1) for lists; random.sample(set, 1) is O(n) due to set-to-list conversion — always maintain an explicit list for getRandom.
• bisect.bisect_right(arr, x) - 1 gives the index of the largest element ≤ x in a sorted array; the result can be -1 if all elements are greater — guard with a bounds check.
• Linked list nodes must be defined as a class or namedtuple; Python dicts cannot store mutable references to bare tuples and have them updated in place.
• collections.deque in Python supports O(1) append and popleft; use it for queue-based design problems rather than a list (list.pop(0) is O(n)).
• When implementing a thread-safe structure conceptually, use threading.Lock as a context manager (with self.lock:); never manually acquire/release — exceptions skip the release.
• sortedcontainers.SortedList (third-party but allowed in interviews with declaration) provides O(log n) add/discard and O(log n) rank queries; it is the practical substitute for a balanced BST in Python.

---

12. Cross-Topic Relations

See doubly-linked-list.md, heap-priority-queue.md, segment-tree.md, data-stream.md for full coverage of those topics.

---

13. Interview Reference

Must-Know Problems

LRU / LFU Cache

• LRU Cache (LC 146) — foundational; must implement cleanly in ~30 lines
• LFU Cache (LC 460) — harder; frequency buckets + min_freq pointer

Stack / Queue Variants

• Min Stack (LC 155)
• Implement Queue using Stacks (LC 232)
• Implement Stack using Queues (LC 225)
• Max Stack (LC 716)

Randomized Structures

• Insert Delete GetRandom O(1) (LC 380) — RandomizedSet
• Insert Delete GetRandom O(1) Duplicates Allowed (LC 381)

Streaming / Statistical

• Find Median from Data Stream (LC 295) — two heaps
• Moving Average from Data Stream (LC 346) — circular buffer
• Sliding Window Median (LC 480) — advanced; two heaps with lazy deletion

Versioned / Time-Series

• Time Based Key-Value Store (LC 981) — TimeMap with bisect
• Snapshot Array (LC 1146) — sparse versioning

Iterators

• Peeking Iterator (LC 284)
• Flatten Nested List Iterator (LC 341)
• Zigzag Iterator (LC 281)
• Flatten 2D Vector (LC 251)

Codec / Serialization

• Serialize and Deserialize Binary Tree (LC 297)
• Serialize and Deserialize BST (LC 449)
• Encode and Decode Strings (LC 271)

Range Query Design

• Range Sum Query — Mutable (LC 307) — BIT or segment tree
• My Calendar I / II / III (LC 729, 731, 732)

Advanced / Hard

• All O(1) Data Structure (LC 432) — doubly linked list of frequency buckets
• Design Twitter (LC 355) — heap merge of multiple sorted feeds
• Design Search Autocomplete System (LC 642) — Trie + priority queue
• Skip List (LC 1206) — probabilistic balanced structure

Clarification Questions to Ask

• What is the capacity? Can it be 0?
• Is the get/put interface the only API, or are there bulk operations?
• For caches: is the eviction policy exactly LRU (recency) or LFU (frequency with recency tie-break)?
• For iterators: can the underlying collection be modified during iteration?
• For TimeMap: are timestamps guaranteed to be strictly increasing per key, or can they repeat?
• For random: should it be uniform over distinct values or over all insertions (matters for duplicates)?
• For thread safety: is the expected concurrency read-heavy (use read-write lock) or write-heavy?
• For serialization: what characters are safe to use as delimiters? Can values contain arbitrary characters?
• For counters/rate limiters: is the window sliding (exact) or tumbling (bucket-based approximation)?

Common Interview Mistakes

• Implementing LRU with an OrderedDict without explaining why (acceptable shortcut if you can explain; not acceptable as a black box).
• Forgetting sentinel nodes and then writing six if node.prev is None guards that hide bugs.
• Confusing move_to_end direction in OrderedDict — calling move_to_end(key, last=True) when you want most-recent at a specific end.
• Setting min_freq += 1 unconditionally on LFU get instead of only when the old bucket is now empty.
• Using list.pop(0) for queue operations inside a design structure — O(n) cost makes the overall complexity wrong.
• Implementing hasNext() with a try/except that calls next() on the underlying iterator — this consumes elements and the double-call contract breaks.
• Forgetting to update the index map for the swapped element in RandomizedSet remove.
• Off-by-one in bisect_right for TimeMap: bisect_right(ts_list, timestamp) - 1 can be -1 (no valid timestamp exists); returning "" in that case is required.
• Building LFU with a heap instead of frequency buckets — correct but O(log n) per operation instead of O(1); penalised on harder problems.
• Not handling the duplicate-key put in LRU: inserting a second node for the same key corrupts all future evictions.

Typical Follow-Up Escalations

• "Your LRU is O(1) average — make the LFU also O(1)." → Add frequency buckets with OrderedDict; introduce min_freq pointer.
• "Make your cache thread-safe." → Wrap all public methods with a threading.Lock; or use read-write lock for get-heavy workloads.
• "Extend TimeMap to support delete." → Add tombstone entries with a sentinel value; adjust bisect search to skip tombstones.
• "Your MedianFinder handles int — now handle a stream of floats with possible duplicates." → No change needed structurally; clarify that heaps handle duplicates correctly.
• "Make RandomizedSet support weighted random." → Store weights alongside elements; use random.choices(population, weights) — O(n) per call unless a prefix-sum structure is added.
• "Design an LRU that also supports O(1) getMin." → Combine LRU (DLL + dict) with MinStack logic — maintain a parallel min-stack that mirrors the DLL order.
• "Your serializer uses commas as delimiters — what if values contain commas?" → Use length-prefixed encoding: "4:abcd,3:xyz" or escape delimiters.
• "Scale your LRU to a distributed system." → Introduce consistent hashing for partitioning; each node runs a local LRU; discuss replication and cache coherence.