Custom Data Structures — How the Pattern Works
Custom Data Structure design composes two or more primitive building blocks (hash maps, doubly linked lists, dynamic arrays, heaps, queues, prefix arrays, or tries) to satisfy simultaneous per-method complexity bounds that no single built-in container achieves alone. Each constituent block handles the exact access pattern it executes fastest—such as O(1) key lookup in a hash map paired with O(1) recency splicing in a doubly linked list, or O(1) append paired with O(log n) binary search—while every mutating method enforces a cross-structure synchronization invariant so all blocks remain consistent. By precomputing auxiliary state incrementally or deferring cross-container cleanup via lazy tombstones, linear O(n) scans on read and eviction paths drop to O(1) or O(log n).
- The prompt asks to design a stateful class (
__init__,get,put,query, etc.) where every method carries a strict O(1) or O(log n) time bound. - Operations demand conflicting access patterns simultaneously, such as O(1) random lookup plus O(1) recency/frequency eviction (LRU, LFU, All O(1)), or O(1) deletion plus O(1) uniform random sampling.
- Immutable or monotonically timestamped data receives high-volume historical, range, or distance queries (Snapshot Array, TimeMap, Prefix Sums, Inverted Word Index).
- Streaming inputs require sliding-window aggregates, suffix dictionary matching, or dual-order extraction (Moving Average, MK Average, StreamChecker, Max Stack).
- Breaking map synchronization when removing the tail element in swap-to-end deletion (
RandomizedSet): always assignindex[last] = ibefore executingdel index[val]soval == lastleavesvaldeleted. - Omitting
prevpointers or dummy sentinelhead/tailnodes in linked caches: singly linked lists degrade node removal to O(n), and unguardedNoneendpoints cause pointer bugs on empty or 1-element lists. - Off-by-one boundary bugs in binary search over versioned histories or half-open intervals
[left, right): whenbisectreturns index0, every stored timestamp is strictly later than the query and must return""orFalserather than indexing[-1]. - Returning tombstoned items in lazy-deletion structures: every top-inspection or removal method (
pop,top,peekMax,popMax) must purge IDs present ingonebefore accessing its container's top.
class Node:
def __init__(self, k=0, v=0, prev=None, nxt=None):
self.key, self.val, self.prev, self.next = k, v, prev, nxt
head, tail, nodes = Node(), Node(), {}
head.next, tail.prev = tail, head
def unlink(node):
node.prev.next, node.next.prev = node.next, node.prev
def insert_front(node):
node.prev, node.next = head, head.next
head.next.prev = head.next = nodevalues, index = [], {}
def insert(val):
if val not in index:
index[val] = len(values)
values.append(val)
def remove(val):
i, last = index[val], values[-1]
values[i], index[last] = last, i
values.pop()
del index[val]def push(stack, heap, x, uid):
stack.append((x, uid))
heapq.heappush(heap, (-x, -uid))
def pop_valid_max(heap, gone):
while -heap[0][1] in gone:
heapq.heappop(heap)
val, neg_id = heapq.heappop(heap)
gone.add(-neg_id)
return -val