Chapter 11 · Composite structures

Composite designs appear when no single structure makes every required operation cheap. Assign each operation to the structure that owns it, then define how their representations stay synchronized.

Operation-to-owner table

Design	Structure A	Structure B	Result
LRU cache	hash map	doubly linked list	O(1) lookup and recency update
LFU cache	key map	frequency buckets + recency lists	O(1) average access and eviction
randomized set	hash map	dynamic array	O(1) expected delete and random
streaming median	max-heap	min-heap	O(log n) add, O(1) median
time map	hash map	sorted history	key lookup plus binary search
min stack	value	prefix minimum	O(1) minimum
Design Twitter	follow graph	per-user feeds + heap merge	recent top-k news feed
All O(1)	key map	ordered count buckets	O(1) increment, decrement, min, max
number containers	index map	per-number ordered indices	update plus smallest-index query
snapshot array	array	per-index sorted histories	sparse versions + binary search

The design method

For every composite problem:

1. list the required operations and target complexity;
2. assign one structure to own each expensive operation;
3. write the cross-structure invariant;
4. specify the exact update order for every mutation;
5. test the boundary where two structures change together.

flowchart LR
  accTitle: Designing and reviewing a composite data structure
  accDescr: Start from the required operations, assign each costly operation to an owning structure, write the synchronization invariant, define mutation order, then test every boundary where ownership moves. A failed boundary test sends the design back to its invariant.
  A["List operations and<br/>target complexity"] --> B["Assign each operation<br/>to an owning structure"]
  B --> C["Write the shared<br/>representation invariant"]
  C --> D["Define mutation order<br/>and cleanup rules"]
  D --> E{"Boundary tests pass?"}
  E -->|no| C
  E -->|yes| F["Stable composite design"]

The invariant is the most important step. “Use a map and a list” is not yet a design; “every map entry points to exactly one live list node, and every real list node has one map entry” is testable.

Choose by the missing operation

Existing structure	Missing operation	Add
array gives random indexing	O(1) deletion by value	value-to-index hash map
hash map gives direct lookup	recency or frequency order	linked bucket list
one heap gives one extreme	middle of a stream	opposite heap
current value only	historical query	append-only version history
ordinary stack	aggregate after pop	prefix aggregate beside each value
adjacency sets	global newest k items	heap-based k-way merge

Detailed problem guides

Seven guides include tested C++11, C++17, and Python implementations:

• LRU cache
• Randomized set
• Streaming median
• Time-based key-value store
• Min stack
• Number containers
• Snapshot array

The remaining guides focus on the ownership model and mutation order for more complex interview designs:

• LFU cache
• Design Twitter
• All O(1) data structure

Composite structures most often fail at synchronization boundaries. Test overwriting, deleting the last array element, moving between buckets, removing an empty bucket, zero/one capacity, duplicate extremes, and queries before the first stored version.

Tested anchor example

LRU cache is the clearest example of two structures owning different operations while representing the same live entries:

PythonC++17C++11

class _LRUNode:
    """One entry in the recency list."""

    __slots__ = ("key", "value", "previous", "next")

    def __init__(self, key: int = 0, value: int = 0) -> None:
        self.key = key
        self.value = value
        self.previous: _LRUNode | None = None
        self.next: _LRUNode | None = None


class LRUCache:
    """Map keys to nodes while a linked list owns recency order."""

    def __init__(self, capacity: int) -> None:
        if capacity < 0:
            raise ValueError("capacity must be nonnegative")
        self.capacity = capacity
        self.nodes: dict[int, _LRUNode] = {}
        self.head, self.tail = _LRUNode(), _LRUNode()
        self.head.next, self.tail.previous = self.tail, self.head

    def _detach(self, node: _LRUNode) -> None:
        # Splice the node out without searching for its neighbors.
        assert node.previous is not None and node.next is not None
        node.previous.next = node.next
        node.next.previous = node.previous

    def _insert_front(self, node: _LRUNode) -> None:
        # The first real node is always the most recently used.
        first = self.head.next
        assert first is not None
        node.previous, node.next = self.head, first
        self.head.next = first.previous = node

    def _touch(self, node: _LRUNode) -> None:
        self._detach(node)
        self._insert_front(node)

    def get(self, key: int) -> int:
        node = self.nodes.get(key)
        if node is None:
            return -1
        # A successful read makes this entry most recent.
        self._touch(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.nodes:
            node = self.nodes[key]
            node.value = value
            self._touch(node)
            return

        node = _LRUNode(key, value)
        self.nodes[key] = node
        self._insert_front(node)
        if len(self.nodes) > self.capacity:
            # Evict the least-recent real node and its map entry together.
            oldest = self.tail.previous
            assert oldest is not None and oldest is not self.head
            self._detach(oldest)
            del self.nodes[oldest.key]

class LRUCache {
 public:
  explicit LRUCache(int capacity) : capacity_(capacity) {
    if (capacity < 0) {
      throw std::invalid_argument("capacity must be nonnegative");
    }
  }

  // The map stores iterators into this instance's list, so shallow copying
  // would leave the copy pointing into the original cache.
  LRUCache(const LRUCache&) = delete;
  LRUCache& operator=(const LRUCache&) = delete;
  LRUCache(LRUCache&&) noexcept = default;
  LRUCache& operator=(LRUCache&&) noexcept = default;

  int get(int key) {
    const auto found = nodes_.find(key);
    if (found == nodes_.end()) {
      return -1;
    }
    // A successful read makes this entry most recent.
    touch(found->second);
    return found->second->second;
  }

  void put(int key, int value) {
    const auto found = nodes_.find(key);
    if (found != nodes_.end()) {
      found->second->second = value;
      touch(found->second);
      return;
    }

    // The list front is most recent; the back is the eviction target.
    recency_.push_front({key, value});
    nodes_[key] = recency_.begin();
    if (nodes_.size() > static_cast<std::size_t>(capacity_)) {
      const int oldest_key = recency_.back().first;
      recency_.pop_back();
      nodes_.erase(oldest_key);
    }
  }

 private:
  using Entry = std::pair<int, int>;
  using Iterator = std::list<Entry>::iterator;

  void touch(Iterator entry) {
    // splice moves the existing node without invalidating its iterator.
    recency_.splice(recency_.begin(), recency_, entry);
  }

  int capacity_;
  std::list<Entry> recency_;
  std::unordered_map<int, Iterator> nodes_;
};

class LRUCache {
 public:
  explicit LRUCache(int capacity) : capacity_(capacity) {
    if (capacity < 0) {
      throw std::invalid_argument("capacity must be nonnegative");
    }
  }

  // The map stores iterators into this instance's list, so shallow copying
  // would leave the copy pointing into the original cache.
  LRUCache(const LRUCache&) = delete;
  LRUCache& operator=(const LRUCache&) = delete;
  LRUCache(LRUCache&&) noexcept = default;
  LRUCache& operator=(LRUCache&&) noexcept = default;

  int get(int key) {
    const auto found = nodes_.find(key);
    if (found == nodes_.end()) {
      return -1;
    }
    // A successful read makes this entry most recent.
    touch(found->second);
    return found->second->second;
  }

  void put(int key, int value) {
    const auto found = nodes_.find(key);
    if (found != nodes_.end()) {
      found->second->second = value;
      touch(found->second);
      return;
    }

    // The list front is most recent; the back is the eviction target.
    recency_.push_front({key, value});
    nodes_[key] = recency_.begin();
    if (nodes_.size() > static_cast<std::size_t>(capacity_)) {
      const int oldest_key = recency_.back().first;
      recency_.pop_back();
      nodes_.erase(oldest_key);
    }
  }

 private:
  using Entry = std::pair<int, int>;
  using Iterator = std::list<Entry>::iterator;

  void touch(Iterator entry) {
    // splice moves the existing node without invalidating its iterator.
    recency_.splice(recency_.begin(), recency_, entry);
  }

  int capacity_;
  std::list<Entry> recency_;
  std::unordered_map<int, Iterator> nodes_;
};