Dashboard/Coding patterns/26. Custom Data Structures

CODING PATTERNS · LESSON 26 OF 28 · 49 MIN VIDEO · 16 PROBLEMS

Custom Data Structures

Module Progress (0 / 16 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (49 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

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).

WHEN TO USE THIS PATTERN
  • 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).
COMMON INTERVIEW PITFALLS
  • Breaking map synchronization when removing the tail element in swap-to-end deletion (RandomizedSet): always assign index[last] = i before executing del index[val] so val == last leaves val deleted.
  • Omitting prev pointers or dummy sentinel head/tail nodes in linked caches: singly linked lists degrade node removal to O(n), and unguarded None endpoints 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): when bisect returns index 0, every stored timestamp is strictly later than the query and must return "" or False rather than indexing [-1].
  • Returning tombstoned items in lazy-deletion structures: every top-inspection or removal method (pop, top, peekMax, popMax) must purge IDs present in gone before accessing its container's top.
Hash Map + Doubly Linked List (O(1) Lookup + Recency Order)Combining O(1) key lookup with O(1) arbitrary node unlinking and front/back insertion (LRU Cache, frequency bucket lists).
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 = node
Dynamic Array + Index Map (Swap-to-End O(1) Deletion)Supporting O(1) insertion, O(1) arbitrary value removal without element shifting, and O(1) uniform random indexing.
values, 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]
Dual Orderings + Lazy Tombstone SetMaintaining identical items across two orderings (e.g., LIFO stack + max-heap) when eager middle removal would cost O(n).
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
🔒 PRO PROBLEMTarget: O(L) per query L = longest word · trie built once

13. Stream of Characters

Pattern Trigger: words ending now → trie of reversed words

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

Say we add a remove method to the score class. What should remove do, so total stays instant?