← All patterns

Custom Data Structs

Compose primitives — hash + linked list, twin heaps, segment trees, balanced BSTs — to satisfy an unusual operation spec in optimal time. LRU, LFU, time-keyed stores, snapshot arrays.

16 problems 4 Easy 6 Medium 6 Hard

Compose primitives to satisfy an unusual operation contract in optimal time. Common compositions: hash + doubly-linked list (LRU), two heaps (median), trie + multiset (Word Filter), segment tree (range queries with updates), balanced BST or `std::map` for ordered queries.

The trick is matching every spec'd operation to an O(log n) or O(1) primitive — any mismatch dominates the runtime.

When to reach for this pattern

  • Design problem: implement X with operations Y, Z each in O(log n) or O(1)
  • Cache eviction policies (LRU, LFU)
  • Time-keyed key-value stores, snapshot arrays
  • Combined ordering + frequency queries

Canonical template 

// LRU cache: hash map of key → list iterator
class LRUCache {
    int cap;
    list<pair<int, int>> dq;
    unordered_map<int, list<pair<int, int>>::iterator> m;
public:
    LRUCache(int c) : cap(c) {}
    int get(int k) {
        auto it = m.find(k);
        if (it == m.end()) return -1;
        dq.splice(dq.begin(), dq, it->second);
        return it->second->second;
    }
    void put(int k, int v) {
        auto it = m.find(k);
        if (it != m.end()) {
            it->second->second = v;
            dq.splice(dq.begin(), dq, it->second);
            return;
        }
        if ((int)dq.size() == cap) {
            m.erase(dq.back().first);
            dq.pop_back();
        }
        dq.emplace_front(k, v);
        m[k] = dq.begin();
    }
};

C++ · adapt the names and types to your problem.

Common pitfalls

  • Mismatched data structures: O(log n) feature in one half wasted by O(n) in the other
  • STL iterator invalidation on erase/insert — list is safer than vector here
  • Snapshot semantics: copy-on-write vs lazy versioning — pick early
  • Two heaps for median: rebalance after *every* operation, not just every other

Related patterns

Hash Maps Heaps Trie

Problems (16)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.