Designing Data Structures

Your phone keeps the three apps you used most recently ready in memory. Open one of them and it appears instantly. Open a fourth, and the phone has to throw one out: the one you have not touched for the longest time.

To do that, the phone needs three things to be fast: find an app by name, mark an app as "just used", and find the least recently used app. No single structure you have met does all three in O(1). An array finds the oldest but not a name. A hash map finds a name but has no idea of order. The answer is to use both, wired together.

#A method for design questions

"Design a structure that supports these operations" problems look open-ended, but the same four steps solve most of them.

1. List the operations and the cost you need for each. Write them down: get in O(1), put in O(1). The target usually decides the design.
2. For each operation, name the structure that makes it cheap. Lookup by key: hash map. Last in, first out: stack. Smallest so far: heap. Order with cheap removal from the middle: doubly linked list.
3. Combine them, and decide what links them. Usually one part stores pointers or indexes into another, so you can jump between them without searching.
4. Keep every part in sync. Each operation must update all parts, or none. Write down the rule that must stay true after every call, and check each method against it.

#Worked design 1: a stack that knows its minimum

You want a stack with push, pop, top and also getMin, all in O(1). A plain stack makes getMin a full scan: O(n).

A first idea is one extra variable holding the smallest value. It handles push fine. Then you pop the smallest value, and you have no idea what the new minimum is without scanning again. The variable forgot the history.

So store the history. Next to every value, record the minimum of the stack at the moment that value was pushed. Keep those in a second stack that grows and shrinks with the first. The top of the second stack is always the current minimum, and popping both together restores the old minimum for free.

class MinStack {
  constructor() {
    this.values = [];
    this.mins = []; // mins[i] = smallest of values[0..i]
  }
  push(x) {
    const currentMin = this.mins.length ? this.mins[this.mins.length - 1] : x;
    this.values.push(x);
    this.mins.push(Math.min(x, currentMin));
  }
  pop() {
    this.mins.pop();
    return this.values.pop();
  }
  top() { return this.values[this.values.length - 1]; }
  getMin() { return this.mins[this.mins.length - 1]; }
}

class MinStack:
    def __init__(self):
        self.values = []
        self.mins = []  # mins[i] = smallest of values[0..i]
 
    def push(self, x):
        current_min = self.mins[-1] if self.mins else x
        self.values.append(x)
        self.mins.append(min(x, current_min))
 
    def pop(self):
        self.mins.pop()
        return self.values.pop()
 
    def top(self):
        return self.values[-1]
 
    def get_min(self):
        return self.mins[-1]

The rule that stays true: mins[i] is the smallest of values[0..i], and both stacks have the same height. push and pop each change both stacks by one, so the rule survives every call.

#Worked design 2: an LRU cache

Back to the phone. An LRU cache ("least recently used") holds at most capacity key-value pairs. get(key) returns the value and counts as a use. put(key, value) adds or replaces a pair, and if the cache is full, first evicts the pair used longest ago. Both must be O(1).

Apply the method:

• Find by key: a hash map.
• Keep items in order of use, move any item to the front, remove from the back: a doubly linked list. With prev and next pointers, unlinking a node from the middle is O(1), as long as you already hold the node.
• The link: the map stores key → node, not key → value. That is how get reaches a node in the middle of the list without walking to it. Each node also stores its own key, so that evicting the last node can delete its map entry.

The list has two dummy nodes, head and tail, called sentinels. They are never removed, so every real node always has a neighbour on each side, and the code never needs an "is the list empty?" special case.

class LRUCache {
  constructor(capacity) { // capacity >= 1
    this.capacity = capacity;
    this.map = new Map(); // key -> node
    this.head = { next: null }; // sentinel on the newest side
    this.tail = { prev: this.head }; // sentinel on the oldest side
    this.head.next = this.tail;
  }
  unlink(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  addFront(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }
  get(key) {
    const node = this.map.get(key);
    if (node === undefined) return null;
    this.unlink(node); // a get counts as a use
    this.addFront(node);
    return node.value;
  }
  put(key, value) {
    if (this.map.has(key)) {
      this.unlink(this.map.get(key));
    } else if (this.map.size === this.capacity) {
      const oldest = this.tail.prev;
      this.unlink(oldest);
      this.map.delete(oldest.key); // why the node stores its key
    }
    const node = { key, value };
    this.addFront(node);
    this.map.set(key, node);
  }
}

class Node:
    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None
 
class LRUCache:
    def __init__(self, capacity):  # capacity >= 1
        self.capacity = capacity
        self.map = {}  # key -> node
        self.head, self.tail = Node(), Node()  # sentinels
        self.head.next, self.tail.prev = self.tail, self.head
 
    def _unlink(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def _add_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node
 
    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return None
        self._unlink(node)  # a get counts as a use
        self._add_front(node)
        return node.value
 
    def put(self, key, value):
        if key in self.map:
            self._unlink(self.map[key])
        elif len(self.map) == self.capacity:
            oldest = self.tail.prev
            self._unlink(oldest)
            del self.map[oldest.key]  # why the node stores its key
        node = Node(key, value)
        self._add_front(node)
        self.map[key] = node

#More pairings worth knowing

• Hash map + array: insert, delete and pick a random item, all O(1). The map stores each value's index. To delete, move the last item into the gap, update its index in the map, and pop the end.
• Two heaps: a running median. A max-heap holds the smaller half, a min-heap the larger half, and the median sits on top. See Heaps and Priority Queues.
• Hash map + heap: a top-k leaderboard where scores change. The map holds current scores; heap entries that no longer match the map are skipped when they reach the top.

#Common mistakes

#Check yourself

#What to practise next

Build the min-stack yourself in Lowest Point on the Trail. Then try Two-Spike Order Rail, a queue made from two stacks, and Live Median House Price, the two-heaps pairing. For a harder design, use the four steps on a queue with enqueue, dequeue and getMax in amortized O(1); Monotonic Stack and Queues and Deques have the parts you need.