Data Structure Design

At a glance

The instinct

Design questions hand you an API - a constructor and a few methods - plus a cost for each method, stated or implied. No single library type satisfies all of them, so the work is composition: one structure answers "where is key X right now?" and another remembers the order the problem cares about (recency, insertion, time, frequency, rank). The map stores pointers or indices into the ordered structure so both views stay consistent.

LRU Cache is a hash map plus a doubly linked list. Insert Delete GetRandom O(1) is a hash map plus an array list with swap-to-end deletion. Time Based Key-Value Store is a hash map from key to an append-only, already-sorted list searched with binary search.

Recognise it

Not this pattern if...

• Only one method really matters and the class is just a wrapper (a Solution class) - solve the algorithm.
• The question is about machines, shards and replication - that is system design, not data structure design.
• One built-in already satisfies every method (for example TreeMap for floor lookups); use it, and say so.

Memory hack

Analogy - the library catalogue. The card catalogue (finder) tells you the exact shelf slot of each book; the shelves (keeper) hold the books in order. If a librarian moves a book and forgets to update its card, the next reader walks to an empty slot. That is exactly the bug when you evict a node from the list but leave its key in the map.

Say it out loud:

1. "Here are the methods and the target cost of each one." (Write a two-column table.)
2. "My finder maps ___ to ___; my keeper is ___ because it gives me ___ in O(1) / O(log n)."
3. "Invariant: a key is in the map if and only if it is in the keeper. Now I'll walk each method, including edge cases like a duplicate key, capacity 1, and an empty structure."

How it works

Follow the same four steps every time: list operations -> choose structures -> state the invariant -> walk each method. The table shows how familiar problems decompose:

The LRU put flow, which is the shape most cache questions follow:

flowchart TD
  P["put(key, value)"] --> Q{"key already in map?"}
  Q -- yes --> R["update value and move node to front"]
  Q -- no --> S["create node, add to front, map.put"]
  S --> T{"size > capacity?"}
  T -- yes --> U["remove tail.prev from the list AND from the map"]
  T -- no --> V["done"]

Java template

import java.util.HashMap;
import java.util.Map;

// Finder (HashMap) + keeper (doubly linked list). Front of the list = most recently used.
class LinkedMapCache<K, V> {
    private static final class Node<K, V> {
        K key; V val; Node<K, V> prev, next;
        Node(K key, V val) { this.key = key; this.val = val; }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null), tail = new Node<>(null, null); // sentinels

    LinkedMapCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        moveToFront(node);                      // touching an entry refreshes its recency
        return node.val;
    }

    void put(K key, V val) {
        Node<K, V> node = map.get(key);
        if (node != null) { node.val = val; moveToFront(node); return; }
        node = new Node<>(key, val);
        map.put(key, node);
        addFront(node);
        if (map.size() > capacity) {            // evict from the back: update BOTH structures
            Node<K, V> lru = tail.prev;
            unlink(lru);
            map.remove(lru.key);
        }
    }

    private void moveToFront(Node<K, V> n) { unlink(n); addFront(n); }
    private void unlink(Node<K, V> n) { n.prev.next = n.next; n.next.prev = n.prev; }
    private void addFront(Node<K, V> n) {
        n.next = head.next; n.prev = head;
        head.next.prev = n; head.next = n;
    }
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

// Finder (value -> index) + keeper (array list): O(1) insert, remove and uniform random.
class IndexedSet<T> {
    private final Map<T, Integer> pos = new HashMap<>();
    private final List<T> items = new ArrayList<>();
    private final Random rng = new Random();

    boolean insert(T x) {
        if (pos.containsKey(x)) return false;
        pos.put(x, items.size());
        items.add(x);
        return true;
    }

    boolean remove(T x) {
        Integer i = pos.remove(x);
        if (i == null) return false;
        T last = items.remove(items.size() - 1);  // O(1): always remove from the end
        if (i < items.size()) {                   // x was not the last one: fill its hole
            items.set(i, last);
            pos.put(last, i);
        }
        return true;
    }

    T getRandom() { return items.get(rng.nextInt(items.size())); }
}

Complexity

Variations

• Eviction caches - recency via a linked list; LRU Cache. LFU adds a frequency -> list map plus a min-frequency pointer.
• Randomised containers - array plus index map with swap-delete; Insert Delete GetRandom O(1).
• Time travel / versioning - per-key or per-index change logs plus binary search; Time Based Key-Value Store, Snapshot Array.
• Navigation history - array with a cursor and a logical end (or two stacks); Design Browser History.
• Frequency-ordered stacks - group elements by how often they appeared; Maximum Frequency Stack.
• Ranked groups with updates - TreeSet per group, or a heap that skips stale entries; Design a Food Rating System.
• Feed merging - per-user timelines merged with a heap of size k; Design Twitter.

Common mistakes

• Handling only the "new key" branch of put; updating an existing key must change its value and its position without growing the size.
• Skipping sentinel head and tail nodes, then drowning in null checks for the first and last elements.
• In swap-delete, forgetting to update the moved element's index - or "moving" the last element onto itself when it was the one being removed.
• Copying the whole array on every snap(): correct but O(n) per snapshot and a memory blowup. Log changes instead.
• Mutating an object that is already inside a PriorityQueue or TreeSet; the structure does not re-sort itself. Remove, update, re-insert, or push a fresh entry and skip stale ones lazily.

All practice problems

8 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.