Design a Data Structure

Some interview questions don’t ask you to solve a problem — they ask you to build a thing: “implement an LRU cache”, “design a data structure that inserts, deletes and returns a random element in O(1)“. These are the design-a-data-structure problems, and they have a signature shape: you’re given a set of operations and a target time complexity for each, and your job is to pick the internal representation that makes all of them fast at once.

The idea

Here is the key realisation: no single built-in structure does everything. A hash map gives you O(1) lookup but has no order. A list or array gives you order but O(n) search. A heap gives you the min/max but not arbitrary lookup. So the move is almost always to combine two structures — one for fast lookup and one for ordering — and carefully keep them consistent on every operation.

That’s the entire pattern. Once you internalise “map for lookup + (list / heap / array) for order, synced on every op”, the specific problems become variations on a theme:

• LRU cache → hash map (key → node) + doubly linked list (recency order).
• LFU cache → hash map + buckets of nodes grouped by frequency.
• Min stack → stack of (value, running-min) pairs.
• Insert/Delete/GetRandom O(1) → array (for random index) + value → index map.
• Time-based key-value store → per-key sorted list + binary search.

The hard part is the bookkeeping: every operation must update both structures so they never disagree. Sentinel (dummy) nodes and small helper methods are what keep that bookkeeping bug-free.

Worked example: LRU cache

An LRU (least-recently-used) cache supports get(key) and put(key, value), both in O(1), and evicts the least-recently-used entry when it exceeds capacity. The map gives O(1) access to any node; the doubly linked list keeps entries in recency order (most-recent at the front, least-recent at the tail). On every touch, we move the node to the front; on overflow, we drop the tail.

The trick that makes the pointer surgery clean is a pair of dummy head and tail sentinel nodes, so _add and _remove never have to special-case the ends of the list:

class Node:
    def __init__(self, k=0, v=0):
        self.k = k; self.v = v; self.prev = None; self.next = None

class LRUCache:
    def __init__(self, cap):
        self.cap = cap; self.m = {}
        self.head = Node(); self.tail = Node()        # dummy sentinels
        self.head.next = self.tail; self.tail.prev = self.head
    def _remove(self, n):
        n.prev.next = n.next; n.next.prev = n.prev
    def _add(self, n):                                 # add right after head
        n.prev = self.head; n.next = self.head.next
        self.head.next.prev = n; self.head.next = n
    def get(self, key):
        if key in self.m:
            n = self.m[key]; self._remove(n); self._add(n)   # touch → front
            return n.v
        return -1
    def put(self, key, val):
        if key in self.m: self._remove(self.m[key])
        n = Node(key, val); self.m[key] = n; self._add(n)
        if len(self.m) > self.cap:
            lru = self.tail.prev                       # least recently used
            self._remove(lru); del self.m[lru.k]
# cap=2: put(1,1) put(2,2) get(1)->1 put(3,3) get(2)->-1 put(4,4) get(1)->-1 get(3)->3 get(4)->4

Every operation touches both the map and the list, and both stay in O(1). That symmetry — find via the map, reorder via the list — is the whole idea.

Worked example: insert / delete / getRandom in O(1)

Design a set that supports insert, remove and getRandom, each in average O(1). getRandom needs an array (random index is O(1)), but removing from the middle of an array is O(n) — unless you swap the element to delete with the last one and pop. A value → index map tells you where each value lives so the swap is O(1):

import random

class RandomizedSet:
    def __init__(self):
        self.idx = {}      # value -> index in arr
        self.arr = []
    def insert(self, val):
        if val in self.idx: return False
        self.idx[val] = len(self.arr); self.arr.append(val); return True
    def remove(self, val):
        if val not in self.idx: return False
        i = self.idx[val]; last = self.arr[-1]
        self.arr[i] = last; self.idx[last] = i          # move last into the hole
        self.arr.pop(); del self.idx[val]; return True
    def getRandom(self):
        return random.choice(self.arr)
# insert(1)->True insert(1)->False remove(2)->False insert(2)->True remove(1)->True

Same pattern: an array for order/random access plus a map for O(1) lookup, kept in sync. The swap-with-last trick is the detail that turns an O(n) delete into O(1).

When to reach for it

Signals that you’re in a design-a-data-structure problem:

• The prompt says “design” or “implement” a class/system with a named set of methods.
• It specifies a target complexity for each operation (“all in O(1)”, “O(log n)”).
• Classic names: LRU / LFU cache, min stack, insert/delete/getRandom, time-based key-value store, design Twitter / a leaderboard / a hit counter, a circular queue.

Your first question should be: which structure makes each operation fast, and can one structure serve more than one operation? When no single one covers everything, combine.

Pitfalls

• Letting the two structures drift apart. The number-one bug: an operation updates the map but forgets the list (or vice versa). Write tiny helpers (_add, _remove) and call them everywhere so the update is atomic and consistent.
• Special-casing the ends of a linked list. Empty list, single node, head, tail — these are where off-by-one bugs live. Use dummy head/tail sentinels so every real node always has a neighbour.
• Getting the eviction order wrong. LRU evicts the tail (least recent); make sure “touch” moves to the front. For LFU, you evict the least-frequently-used and break ties by recency — track a minFreq so eviction stays O(1).
• O(n) hiding in an operation. Removing from the middle of an array, or scanning for the min, quietly breaks the complexity target. The swap-with-last and running-min tricks exist precisely to avoid that.

Recap

Design-a-data-structure problems give you a set of operations with target complexities; you hit them by combining a hash map (lookup) with an ordering structure (linked list / heap / array) and keeping both in sync on every operation. LRU = map + doubly linked list with dummy sentinels; O(1) insert/delete/getRandom = array + index map with swap-with-last. Signal: “design/implement a class with these operations in O(1)/O(log n).”

Practice: 10 solved design problems → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 28 — Study Plan & Curated Lists, how to put the whole course to work.