PATTERN 21 OF 22

Design-Focused DSA

Master class-based data structure design problems that combine multiple data structures for O(1) operations. Learn the hash map + doubly linked list pattern for LRU/LFU caches, multi-map coordination, and the art of trading space for time in interview design problems.

Time: O(1) per get/put operation (amortized)

Space: O(capacity) for cache storage

Learn & Reference

Understanding the Pattern

Design-Focused DSA Pattern

Design-focused DSA problems ask you to build a class (or set of classes) that supports multiple operations, each with strict time complexity requirements. Unlike standard algorithm problems where you write a single function, these problems require you to choose and combine data structures so that every public method meets its O(1) or O(log n) contract.

Core Concept

The central idea is combining two or more data structures so that each one compensates for the other's weakness. A hash map gives O(1) lookup by key but has no concept of ordering. A doubly linked list maintains insertion order and supports O(1) removal (given a node reference) but has no fast lookup. Combine them and you get O(1) lookup AND O(1) order-aware removal — the foundation of LRU Cache.

Hash Map + Doubly Linked List = O(1) ordered cache

HashMap:  key -> Node reference (O(1) lookup)
DLL:     head <-> [A] <-> [B] <-> [C] <-> tail  (O(1) add/remove)

get(key):
  1. HashMap lookup -> Node       O(1)
  2. Remove Node from DLL         O(1) (have the reference)
  3. Move Node to head of DLL     O(1)

put(key, val):
  1. If exists: update + move to head    O(1)
  2. If new: create Node, add to head    O(1)
  3. If over capacity: remove tail node  O(1)
     Also remove from HashMap            O(1)

Key Techniques

1. Hash Map + Doubly Linked List (LRU Cache)

This is the most common design pattern in interviews. The hash map stores key -> node mappings for O(1) access, and the doubly linked list maintains recency order. When an item is accessed, move it to the front. When capacity is exceeded, evict from the tail.

The doubly linked list uses sentinel nodes (dummy head and dummy tail) to eliminate null-check edge cases. Every insertion and removal is between two existing nodes, so the code is uniform.

Sentinel DLL structure:
  dummyHead <-> [MRU] <-> ... <-> [LRU] <-> dummyTail

Remove node X:
  X.prev.next = X.next
  X.next.prev = X.prev

Insert node X after dummyHead:
  X.next = dummyHead.next
  X.prev = dummyHead
  dummyHead.next.prev = X
  dummyHead.next = X

2. Multi-Map Coordination (LFU Cache)

LFU (Least Frequently Used) cache extends the pattern with three coordinated maps:

keyToNode: maps key to its node (value, frequency)
freqToList: maps each frequency to a doubly linked list of nodes at that frequency
minFreq: tracks the current minimum frequency for O(1) eviction

On access, a node's frequency increases by 1: remove it from the old frequency list, add it to the new frequency list. If the old frequency list becomes empty and it was minFreq, increment minFreq. On eviction, remove the tail of freqToList[minFreq].

3. Class Design Skeleton

Every design problem follows the same structure:

Constructor: initialize your data structures and any capacity/configuration
Core methods: implement each operation using your chosen data structures
Helper methods: extract repeated pointer operations (like _remove, _addToHead) into private helpers

The key insight: design your helpers first, then the public methods become 3-5 line functions that compose the helpers.

4. Time-Space Tradeoffs

Design problems explicitly trade space for time. Maintaining a second (or third) data structure costs O(n) extra space, but it buys you O(1) operations that would otherwise be O(n). Common tradeoffs:

Extra hash map for reverse lookup: O(n) space, O(1) reverse access
Doubly linked list alongside hash map: O(n) space, O(1) ordered removal
Frequency buckets: O(n) space, O(1) frequency-based eviction

5. Lazy Deletion

Some design problems benefit from lazy deletion — instead of immediately removing stale entries, mark them as invalid and skip them when encountered during future operations. This is useful when:

Direct deletion is expensive (e.g., removing from a heap is O(n))
The data structure doesn't support efficient targeted removal
Entries naturally expire and are cleaned up during normal access

Recognizing Design Problems

Design problems always provide:

A class name and constructor signature
Multiple methods with specified return types
Explicit time complexity requirements (usually O(1) for all operations)
A capacity constraint or size limit

The challenge is never about a clever algorithm — it is about choosing the right combination of data structures and wiring them together correctly.

Common Mistakes

Not using sentinel nodes in doubly linked lists: Without dummy head and tail nodes, every insertion and removal needs special cases for empty list, single element, head removal, and tail removal. Sentinels eliminate all of these — always use them
Forgetting to update ALL data structures on every operation: If you have a hash map and a linked list, every put/get/delete must update both. Forgetting to remove a key from the hash map when evicting from the linked list causes stale references and wrong capacity counts
Getting DLL pointer operations out of order: When inserting or removing a node, the order of pointer assignments matters. Drawing the before/after state and numbering the steps prevents bugs. A common error is overwriting a next pointer before saving the reference you still need
Not handling the "update existing key" case in put(): Many candidates handle only the "insert new key" path. If put(key, newValue) is called with an existing key, you must update the value AND move the node to the front (LRU) or update its frequency (LFU) — not insert a duplicate
Tracking minFreq incorrectly in LFU: When a node is accessed and its frequency increases from f to f+1, if the frequency-f list becomes empty AND minFreq == f, you must increment minFreq. Forgetting this causes eviction from the wrong frequency bucket
Making helpers that allocate unnecessarily: The point of O(1) operations is to avoid allocation in hot paths. Your _remove and _addToHead helpers should rewire pointers in place, not create new nodes

When to Use

Design a data structure that supports... with multiple operations

Implement a class with get() and put() in O(1)

LRU Cache, LFU Cache, or any cache eviction policy

All operations must be O(1) time complexity

Problems that require combining hash maps with linked lists

Time-based key-value stores or ordered data structures

Any problem where a single data structure cannot meet all time complexity requirements

Class-based problems with constructor, multiple methods, and capacity constraints

Keywords: design, cache, O(1), get, put, capacity, evict, least recently used, least frequently used, class, implement

Template

1# --- Design-Focused DSA Template: Cache with DLL + HashMap ---
2
3class DLLNode:
4    """Doubly linked list node storing key-value pair."""
5    def __init__(self, key=0, val=0):
6        self.key = key
7        self.val = val
8        self.prev = None
9        self.next = None
10
11class Cache:
12    def __init__(self, capacity: int):
13        self.capacity = capacity
14        self.cache = {}           # key -> DLLNode
15        # Sentinel nodes eliminate edge cases
16        self.head = DLLNode()     # dummy head (MRU side)
17        self.tail = DLLNode()     # dummy tail (LRU side)
18        self.head.next = self.tail
19        self.tail.prev = self.head
20
21    def _remove(self, node: DLLNode) -> None:
22        """Remove a node from anywhere in the DLL. O(1)."""
23        node.prev.next = node.next
24        node.next.prev = node.prev
25
26    def _add_to_head(self, node: DLLNode) -> None:
27        """Insert a node right after the dummy head (MRU position). O(1)."""
28        node.next = self.head.next
29        node.prev = self.head
30        self.head.next.prev = node
31        self.head.next = node
32
33    def get(self, key: int) -> int:
34        if key not in self.cache:
35            return -1
36        node = self.cache[key]
37        self._remove(node)
38        self._add_to_head(node)  # mark as recently used
39        return node.val
40
41    def put(self, key: int, value: int) -> None:
42        if key in self.cache:
43            node = self.cache[key]
44            node.val = value
45            self._remove(node)
46            self._add_to_head(node)
47        else:
48            node = DLLNode(key, value)
49            self.cache[key] = node
50            self._add_to_head(node)
51            if len(self.cache) > self.capacity:
52                lru = self.tail.prev  # least recently used
53                self._remove(lru)
54                del self.cache[lru.key]

{ }

Syntax Reference

1# --- Python: OrderedDict (built-in LRU building block) ---
2from collections import OrderedDict
3
4od = OrderedDict()
5
6# Insert / update (appends to end)
7od[key] = value
8
9# Access (does NOT move to end — use move_to_end)
10val = od[key]               # KeyError if missing
11val = od.get(key, default)  # returns default if missing
12
13# Move to end (most recently used)
14od.move_to_end(key)                  # move to end (MRU)
15od.move_to_end(key, last=False)      # move to front (LRU end)
16
17# Pop oldest (least recently used)
18oldest_key, oldest_val = od.popitem(last=False)  # FIFO pop
19
20# Pop newest (most recently used)
21newest_key, newest_val = od.popitem(last=True)   # LIFO pop
22
23# Check existence / size
24key in od           # O(1)
25len(od)             # O(1)
26
27# Delete specific key
28del od[key]         # O(1)
29
30# --- Doubly Linked List Node (manual approach) ---
31class DLLNode:
32    def __init__(self, key=0, val=0):
33        self.key = key
34        self.val = val
35        self.prev = None
36        self.next = None

📋

Common Recipes

1# --- LRU Cache (OrderedDict approach) ---
2from collections import OrderedDict
3
4class LRUCache:
5    def __init__(self, capacity: int):
6        self.capacity = capacity
7        self.cache = OrderedDict()
8
9    def get(self, key: int) -> int:
10        if key not in self.cache:
11            return -1
12        self.cache.move_to_end(key)  # mark as recently used
13        return self.cache[key]
14
15    def put(self, key: int, value: int) -> None:
16        if key in self.cache:
17            self.cache.move_to_end(key)
18        self.cache[key] = value
19        if len(self.cache) > self.capacity:
20            self.cache.popitem(last=False)  # evict oldest
21
22# --- LRU Cache (Manual DLL + HashMap) ---
23class DLLNode:
24    def __init__(self, key=0, val=0):
25        self.key = key
26        self.val = val
27        self.prev = None
28        self.next = None
29
30class LRUCacheManual:
31    def __init__(self, capacity: int):
32        self.capacity = capacity
33        self.cache = {}  # key -> DLLNode
34        self.head = DLLNode()  # sentinel
35        self.tail = DLLNode()  # sentinel
36        self.head.next = self.tail
37        self.tail.prev = self.head
38
39    def _remove(self, node):
40        node.prev.next = node.next
41        node.next.prev = node.prev
42
43    def _add_to_head(self, node):
44        node.next = self.head.next
45        node.prev = self.head
46        self.head.next.prev = node
47        self.head.next = node
48
49    def get(self, key):
50        if key not in self.cache:
51            return -1
52        node = self.cache[key]
53        self._remove(node)
54        self._add_to_head(node)
55        return node.val
56
57    def put(self, key, value):
58        if key in self.cache:
59            node = self.cache[key]
60            node.val = value
61            self._remove(node)
62            self._add_to_head(node)
63        else:
64            node = DLLNode(key, value)
65            self.cache[key] = node
66            self._add_to_head(node)
67            if len(self.cache) > self.capacity:
68                lru = self.tail.prev
69                self._remove(lru)
70                del self.cache[lru.key]
71
72# --- Time-Based Key-Value Store Pattern ---
73import bisect
74
75class TimeMap:
76    def __init__(self):
77        self.store = {}  # key -> [(timestamp, value)]
78
79    def set(self, key, value, timestamp):
80        if key not in self.store:
81            self.store[key] = []
82        self.store[key].append((timestamp, value))
83
84    def get(self, key, timestamp):
85        if key not in self.store:
86            return ""
87        pairs = self.store[key]
88        i = bisect.bisect_right(pairs, (timestamp, chr(127))) - 1
89        return pairs[i][1] if i >= 0 else ""

O(n)

Complexity

Operation	Time	Space
LRU Cache get()	O(1)	O(capacity)
LRU Cache put()	O(1)	O(capacity)
LFU Cache get()	O(1)	O(capacity)
LFU Cache put()	O(1)	O(capacity)
DLL insert (given position)	O(1)	O(1)
DLL remove (given node ref)	O(1)	O(1)
HashMap lookup	O(1) avg	O(n)
Total space (cache of capacity c)	-	O(c)

Watch Out

✗Not using sentinel nodes in doubly linked lists: Without dummy head and tail nodes, every insertion and removal needs special cases for empty list, single element, head removal, and tail removal. Sentinels eliminate all of these — always use them
✗Forgetting to update ALL data structures on every operation: If you have a hash map and a linked list, every put/get/delete must update both. Forgetting to remove a key from the hash map when evicting from the linked list causes stale references and wrong capacity counts
✗Getting DLL pointer operations out of order: When inserting or removing a node, the order of pointer assignments matters. Drawing the before/after state and numbering the steps prevents bugs. A common error is overwriting a `next` pointer before saving the reference you still need
✗Not handling the "update existing key" case in put(): Many candidates handle only the "insert new key" path. If `put(key, newValue)` is called with an existing key, you must update the value AND move the node to the front (LRU) or update its frequency (LFU) — not insert a duplicate
✗Tracking minFreq incorrectly in LFU: When a node is accessed and its frequency increases from `f` to `f+1`, if the frequency-`f` list becomes empty AND `minFreq == f`, you must increment `minFreq`. Forgetting this causes eviction from the wrong frequency bucket
✗Making helpers that allocate unnecessarily: The point of O(1) operations is to avoid allocation in hot paths. Your `_remove` and `_addToHead` helpers should rewire pointers in place, not create new nodes

PRACTICE PROBLEMS

Tries

Bit Manipulation