Design Data Structures

Chapter 38: Design Data Structures

There is a category of interview problems that does not test "which algorithm to use" but rather "can you design a data structure from scratch." The problem gives you a set of API interfaces and performance constraints—usually O(1) time complexity—and asks you to choose the underlying storage scheme, combine multiple fundamental structures, and implement all interfaces while meeting every constraint.

The core competency tested is not template memorization but the ability to decompose requirements into data structure properties. "Needs O(1) lookup" implies a hash table; "needs to maintain order" implies a linked list or array; "needs O(1) removal of the oldest element" implies a queue interface. When a single data structure cannot satisfy all constraints, you must combine two or three structures, linking them through pointers or indices.

This chapter starts with the classic LRU Cache, extends to LFU Cache, Min Stack, Randomized Set, and Twitter Timeline design, then discusses cache eviction strategies in production systems and a general problem-solving framework for design questions in interviews.

Level 1 · What You Need to Know

38.1 LRU Cache Complete Implementation (LeetCode #146)

Problem Statement

Design a data structure that satisfies the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class:

• LRUCache(capacity): Initialize the LRU cache with positive size capacity
• get(key): Return the value of the key if it exists, otherwise return -1
• put(key, value): Update the value if key exists; insert if it does not. When the cache reaches capacity, evict the least recently used item before inserting a new one

Requirement: Both get and put must run in O(1) time complexity.

Why Hash Table + Doubly Linked List?

Let us analyze the core requirement of each operation:

The hash table provides O(1) lookup from key to linked list node pointer; the doubly linked list provides O(1) move and delete operations (because a doubly linked list node knows its predecessor and successor). Only their combination satisfies all O(1) constraints.

If you only use a hash table: you cannot determine "which is least recently used" in O(1)—you need additional order maintenance. If you only use a linked list: you cannot look up a node by key in O(1)—you must traverse.

This is one of the classic online competitive strategies analyzed by Sleator and Tarjan (1985, "Amortized Efficiency of List Update and Paging Rules"), where LRU was proven to be a k-competitive page replacement algorithm.

Complete Implementation

class DLinkedNode:
    """Doubly linked list node"""
    __slots__ = ('key', 'value', 'prev', 'next')
    
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    """
    Hash Table + Doubly Linked List implementation of LRU Cache
    
    Design:
    - Hash table cache: key -> DLinkedNode, provides O(1) lookup
    - Doubly linked list: maintains access order, head is most recent, tail is least recent
    - Sentinel nodes head/tail: simplify boundary condition handling, never deleted
    """
    
    def __init__(self, capacity: int):
        self.cache = {}           # key -> DLinkedNode
        self.capacity = capacity
        self.size = 0
        
        # Sentinel nodes (dummy nodes)
        # Benefit: no special cases for empty list or single-node list
        self.head = DLinkedNode()  # dummy head
        self.tail = DLinkedNode()  # dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # Cache hit: move node to head (mark as most recently used)
        node = self.cache[key]
        self._move_to_head(node)
        return node.value
    
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # Key exists: update value and move to head
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
        else:
            # Key does not exist: create new node
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self._add_to_head(node)
            self.size += 1
            
            if self.size > self.capacity:
                # Over capacity: remove tail node (least recently used)
                removed = self._remove_tail()
                del self.cache[removed.key]  # Node stores key, enabling O(1) hash deletion
                self.size -= 1
    
    def _add_to_head(self, node: DLinkedNode) -> None:
        """Add node right after the head sentinel"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node: DLinkedNode) -> None:
        """Remove a node from the list (O(1) because we know prev and next)"""
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _move_to_head(self, node: DLinkedNode) -> None:
        """Move node to head = remove then add to head"""
        self._remove_node(node)
        self._add_to_head(node)
    
    def _remove_tail(self) -> DLinkedNode:
        """Remove the node before the tail sentinel and return it"""
        node = self.tail.prev
        self._remove_node(node)
        return node

Why Does the Node Store the Key?

Notice that DLinkedNode stores both key and value. The value is obviously needed (get returns it), but why store the key? Because when the cache is full and we evict from the tail, we get a node from the linked list and need to simultaneously remove the corresponding entry from the hash table—if the node does not store the key, we cannot locate the hash table entry in O(1).

Why Use Sentinel Nodes?

A linked list implementation without sentinels requires extensive if-else checks:

# Without sentinels (counterexample)
def _add_to_head(self, node):
    if self.head is None:       # Empty list
        self.head = node
        self.tail = node
    else:
        node.next = self.head
        self.head.prev = node
        self.head = node

Sentinel nodes ensure the list is never empty (at least head and tail sentinels exist), unifying all operation logic and reducing bugs. This is the implementation technique recommended by Cormen et al. in Introduction to Algorithms (CLRS, 3rd Ed, 2009), Section 10.2.

Common Mistakes and Fixes

Complexity Analysis

• Time complexity: get O(1), put O(1)
• Space complexity: O(capacity), hash table and list each store capacity nodes

38.2 LFU Cache Complete Implementation (LeetCode #460)

Problem Statement

Design a data structure satisfying LFU (Least Frequently Used) cache constraints:

• LFUCache(capacity): Initialize
• get(key): Return value for key (frequency +1), return -1 if not found
• put(key, value): Insert or update. When full, evict the key with lowest frequency; if multiple keys share the lowest frequency, evict the least recently used among them

Why Is LFU Harder Than LRU?

LRU maintains only one dimension: time. LFU maintains two dimensions: frequency and time order within the same frequency. The eviction rule becomes "first select minimum frequency, then apply LRU among ties."

Data Structure Selection

We need O(1) for the following operations:

1. Lookup node by key → hash table key_to_node
2. Get current minimum frequency → variable min_freq
3. Evict LRU node from minimum frequency bucket → each frequency maps to a doubly linked list
4. Move node from frequency f list to frequency f+1 list → hash table freq_to_list

Core design: two hash tables + multiple doubly linked lists + one min_freq variable.

This design was proposed by Shah, Mitra, and Matani (2010, "An O(1) algorithm for implementing the LFU cache eviction scheme"), proving all operations can be completed in O(1).

from collections import defaultdict, OrderedDict


class LFUCache:
    """
    LFU Cache: O(1) get/put
    
    Core data structures:
    - key_to_val: dict, key -> value
    - key_to_freq: dict, key -> current frequency
    - freq_to_keys: dict, freq -> OrderedDict (used as ordered set, maintaining LRU order)
    - min_freq: int, current minimum frequency
    
    Why OrderedDict?
    Python's OrderedDict is internally a hash table + doubly linked list, providing:
    - O(1) append to end
    - O(1) delete by key (internal hash table)
    - O(1) pop oldest element (popitem(last=False))
    - O(1) move_to_end
    
    It is exactly the "LRU list within a frequency bucket" that we need.
    """
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_to_val = {}
        self.key_to_freq = {}
        self.freq_to_keys = defaultdict(OrderedDict)
        self.min_freq = 0
    
    def get(self, key: int) -> int:
        if key not in self.key_to_val:
            return -1
        self._increase_freq(key)
        return self.key_to_val[key]
    
    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        
        if key in self.key_to_val:
            self.key_to_val[key] = value
            self._increase_freq(key)
        else:
            if len(self.key_to_val) >= self.capacity:
                self._evict()
            
            self.key_to_val[key] = value
            self.key_to_freq[key] = 1
            self.freq_to_keys[1][key] = None  # Using OrderedDict as OrderedSet
            self.min_freq = 1  # New key has frequency 1, so min_freq must be 1
    
    def _increase_freq(self, key: int) -> None:
        """Increment key's frequency by 1, maintain min_freq"""
        freq = self.key_to_freq[key]
        self.key_to_freq[key] = freq + 1
        
        # Remove from old frequency bucket
        del self.freq_to_keys[freq][key]
        
        # If old bucket is empty and it was min_freq, update min_freq
        if not self.freq_to_keys[freq]:
            del self.freq_to_keys[freq]
            if self.min_freq == freq:
                self.min_freq = freq + 1
        
        # Add to new frequency bucket (end = most recently used)
        self.freq_to_keys[freq + 1][key] = None
    
    def _evict(self) -> None:
        """Evict the LRU key from the min_freq bucket"""
        evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
        
        if not self.freq_to_keys[self.min_freq]:
            del self.freq_to_keys[self.min_freq]
        
        del self.key_to_val[evict_key]
        del self.key_to_freq[evict_key]

Key Insight: Maintaining min_freq

When does min_freq change?

1. When inserting a new key: new key has frequency 1, so min_freq = 1 (the only deterministic assignment)
2. When frequency increases: if the min_freq bucket becomes empty, min_freq += 1

No need to scan all frequency buckets to find the minimum—frequency can only increment by 1, never jump.

LRU vs LFU Comparison

38.3 Min Stack (LeetCode #155)

Problem Statement

Design a stack that supports O(1) push, pop, top, and getMin.

Core Insight

A normal stack naturally supports O(1) push/pop/top. The challenge is getMin—how do you know the current minimum in O(1) after the top element is popped?

Key observation: the minimum is tied to the stack's state. When the stack has n elements, there is a corresponding minimum; when it becomes n-1 elements, there may be a different minimum. So we record the minimum for each "historical state" of the stack.

Two implementation approaches:

1. Auxiliary stack: An extra stack min_stack whose top is always the current state's minimum
2. Tuple approach: Each element in the main stack stores (value, current_min)

class MinStack:
    """
    Auxiliary stack implementation
    
    Why does this work?
    Because a stack is LIFO. If the current minimum m is at depth k,
    then m can only disappear when level k is popped.
    But before level k is popped, levels k+1...n must have already been popped.
    So the changes to minimum also follow a "stack-like" pattern—using a stack to track them is natural.
    """
    
    def __init__(self):
        self.stack = []
        self.min_stack = []  # min_stack[i] = minimum among first i+1 elements
    
    def push(self, val: int) -> None:
        self.stack.append(val)
        # Push to min_stack if empty or val <= current min
        # Note: <= not <. Same minimum value may appear multiple times
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
    
    def pop(self) -> None:
        val = self.stack.pop()
        # If popped value equals current minimum, pop from min_stack too
        if val == self.min_stack[-1]:
            self.min_stack.pop()
    
    def top(self) -> int:
        return self.stack[-1]
    
    def getMin(self) -> int:
        return self.min_stack[-1]

Common Bug: Using < Instead of <=

If you use val < self.min_stack[-1] (strict less than) during push, then when the same minimum value appears twice, min_stack only records it once. After popping one instance of the minimum, min_stack also pops, but there is still another instance of the same minimum in the stack.

# Bug example
stack.push(0)    # min_stack = [0]
stack.push(0)    # min_stack = [0]  <- with <, second 0 won't enter min_stack
stack.pop()      # pop 0, min_stack.pop() -> min_stack = []
stack.getMin()   # ERROR! min_stack is empty but stack still has a 0

38.4 Randomized Set O(1) Insert/Delete/GetRandom (LeetCode #380)

Problem Statement

Design a data structure supporting the following operations in average O(1):

• insert(val): Insert val if not present, return True; otherwise return False
• remove(val): Remove val if present, return True; otherwise return False
• getRandom(): Return a random element from the current set with equal probability

Why Is a Hash Table Not Enough?

A hash table can insert and delete in O(1), but cannot randomly access in O(1)—you cannot "randomly pick a position" in a hash table in O(1) (the internal array has many empty slots).

An array can randomly access in O(1) (random index), but cannot delete a middle element in O(1) (requires shifting subsequent elements).

Solution: Array + Hash Table

• Array nums stores all elements
• Hash table val_to_idx stores each element's index in the array
• Deletion uses the "swap to end then pop" trick for O(1)

import random


class RandomizedSet:
    """
    Array + Hash Table
    
    Core trick: when deleting, swap the target element with the last element,
    then pop from the end. No need to shift other elements, maintaining O(1).
    """
    
    def __init__(self):
        self.nums = []           # stores element values
        self.val_to_idx = {}     # element value -> index in nums
    
    def insert(self, val: int) -> bool:
        if val in self.val_to_idx:
            return False
        self.val_to_idx[val] = len(self.nums)
        self.nums.append(val)
        return True
    
    def remove(self, val: int) -> bool:
        if val not in self.val_to_idx:
            return False
        
        # Swap val with last element
        idx = self.val_to_idx[val]
        last = self.nums[-1]
        
        self.nums[idx] = last
        self.val_to_idx[last] = idx
        
        # Remove from end
        self.nums.pop()
        del self.val_to_idx[val]
        
        return True
    
    def getRandom(self) -> int:
        return random.choice(self.nums)

Why Does "Swap to End" Work?

A set is unordered, so element positions in the array are irrelevant. Swapping does not change the logical content of the set, but turns the physical deletion into an O(1) pop operation.

38.5 Design Twitter (LeetCode #355)

Problem Statement

Design a simplified Twitter:

• postTweet(userId, tweetId): Post a tweet
• getNewsFeed(userId): Get the 10 most recent tweets from user and followees (reverse chronological)
• follow(followerId, followeeId): Follow
• unfollow(followerId, followeeId): Unfollow

This Is a Classic "Merge K Sorted Lists" Scenario

Each user's tweets are ordered by time. Getting a news feed requires merging the tweet lists of the user and all followees, taking the top 10. This is exactly the "merge K sorted lists, take top N" problem—use a max-heap (by timestamp).

import heapq
from collections import defaultdict


class Twitter:
    """
    Design:
    - Global timestamp self.time, incremented on each tweet
    - self.tweets[userId]: list of (timestamp, tweetId), chronological order
    - self.following[userId]: set of followeeIds
    
    getNewsFeed uses heap to merge K sorted lists (at most 10 items per user)
    """
    
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)       # userId -> [(time, tweetId), ...]
        self.following = defaultdict(set)     # userId -> set of followeeIds
    
    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.time, tweetId))
        self.time += 1
    
    def getNewsFeed(self, userId: int) -> list:
        # Collect all relevant users (self + followed)
        users = self.following[userId] | {userId}
        
        # Max-heap merge (Python uses min-heap, negate timestamps)
        heap = []
        for uid in users:
            tweet_list = self.tweets[uid]
            if tweet_list:
                idx = len(tweet_list) - 1
                t, tid = tweet_list[idx]
                heapq.heappush(heap, (-t, tid, uid, idx))
        
        result = []
        while heap and len(result) < 10:
            neg_t, tid, uid, idx = heapq.heappop(heap)
            result.append(tid)
            if idx > 0:
                idx -= 1
                t, tid = self.tweets[uid][idx]
                heapq.heappush(heap, (-t, tid, uid, idx))
        
        return result
    
    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId != followeeId:
            self.following[followerId].add(followeeId)
    
    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)

Time Complexity Analysis

• postTweet: O(1)
• follow/unfollow: O(1)
• getNewsFeed: O(K log K + 10 log K), where K is the number of followed users. Initial heap construction O(K log K), each pop-and-push O(log K), at most 10 times. For social networks with bounded follower counts, this is effectively constant time.

Level 2 · How It Works Internally

38.6 LRU Cache Internal Execution Trace

Let us trace the complete execution of an LRU Cache with a concrete example:

capacity = 3
Operations: put(1,A), put(2,B), put(3,C), get(2), put(4,D), get(1), get(3)

Initial state:

List: head <-> tail
Hash table: {}
size: 0

put(1, A):

List: head <-> [1:A] <-> tail
Hash table: {1: node_1}
size: 1

put(2, B):

List: head <-> [2:B] <-> [1:A] <-> tail
Hash table: {1: node_1, 2: node_2}
size: 2

New nodes are always inserted at the head.

put(3, C):

List: head <-> [3:C] <-> [2:B] <-> [1:A] <-> tail
Hash table: {1: node_1, 2: node_2, 3: node_3}
size: 3 (full)

get(2) -> returns B:

List: head <-> [2:B] <-> [3:C] <-> [1:A] <-> tail
                ^ moved to head
Hash table unchanged

Node 2 is accessed, detached from its position and moved to head.

put(4, D): capacity full, eviction needed

Evict tail.prev = node_1 (least recently used)
Delete cache[1]

List: head <-> [4:D] <-> [2:B] <-> [3:C] <-> tail
Hash table: {2: node_2, 3: node_3, 4: node_4}
size: 3

get(1) -> returns -1: key 1 has been evicted.

get(3) -> returns C:

List: head <-> [3:C] <-> [4:D] <-> [2:B] <-> tail

38.7 OrderedDict-Based LRU Implementation

Python's collections.OrderedDict is internally a hash table + doubly linked list. We can implement LRU's core logic concisely:

from collections import OrderedDict


class LRUCacheSimple(OrderedDict):
    """LRU Cache using OrderedDict (concise version after demonstrating you understand internals)"""
    
    def __init__(self, capacity: int):
        super().__init__()
        self.capacity = capacity
    
    def get(self, key: int) -> int:
        if key not in self:
            return -1
        self.move_to_end(key)  # Mark as most recently used
        return self[key]
    
    def put(self, key: int, value: int) -> None:
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last=False)  # Pop oldest (from head)

OrderedDict.move_to_end(key) and popitem(last=False) are both O(1).

In interviews, you are typically expected to hand-write the doubly linked list because the test is whether you understand the underlying data structure. Using OrderedDict shows "knowing the tool exists"; hand-writing shows "knowing how it works."

38.8 LFU Frequency Bucket Structure In Detail

Let us visualize LFU's internal state:

capacity = 3
Operations: put(1,A), put(2,B), put(3,C), get(1), get(1), get(2), put(4,D)

After put(1,A), put(2,B), put(3,C):

key_to_val:  {1:A, 2:B, 3:C}
key_to_freq: {1:1, 2:1, 3:1}
freq_to_keys: {1: OrderedDict([1, 2, 3])}   <- in insertion order
min_freq: 1

After get(1), get(1):

key_to_val:  {1:A, 2:B, 3:C}
key_to_freq: {1:3, 2:1, 3:1}
freq_to_keys: {1: OrderedDict([2, 3]),  3: OrderedDict([1])}
min_freq: 1

Key 1's frequency becomes 3 (initial 1 + two gets).

After get(2):

key_to_freq: {1:3, 2:2, 3:1}
freq_to_keys: {1: OrderedDict([3]),  2: OrderedDict([2]),  3: OrderedDict([1])}
min_freq: 1

put(4, D): capacity full, evict from min_freq=1 bucket's LRU -> key 3

Evict key 3
key_to_val:  {1:A, 2:B, 4:D}
key_to_freq: {1:3, 2:2, 4:1}
freq_to_keys: {1: OrderedDict([4]),  2: OrderedDict([2]),  3: OrderedDict([1])}
min_freq: 1    <- newly inserted key 4 has frequency 1

38.9 The "Swap-Delete" Trick Deep Dive

"Swap to end then delete" is a technique that recurs in multiple scenarios. Let us understand why it is correct:

Invariant: Array nums[0..n-1] stores all n elements, val_to_idx[v] is v's index in nums.

Atomic steps of delete operation:

1. idx = val_to_idx[val]       # Find position of element to delete
2. last = nums[-1]             # Remember last element
3. nums[idx] = last            # Overwrite target position with last element
4. val_to_idx[last] = idx      # Update last element's index mapping
5. nums.pop()                  # Delete from end (O(1))
6. del val_to_idx[val]         # Delete hash table mapping

Edge case: If val is the last element (idx == len(nums) - 1), steps 3-4 are self-assignment (harmless), steps 5-6 correctly delete.

Why Is getRandom Uniform?

random.choice(nums) uniformly selects an index over a contiguous array, giving each element exactly 1/n probability. With a hash table, due to non-uniform distribution from open addressing or chaining, uniform probability cannot be guaranteed.

38.10 Performance Analysis Framework for Design Problems

For design problems, interviewers typically follow up with performance questions:

Level 3 · What the Specifications Define

38.11 LRU in Operating Systems

Page Replacement Algorithms

Operating system virtual memory management must decide "physical memory is full—which page should be swapped out?" Belady (1966, "A Study of Replacement Algorithms for a Virtual-Storage Computer") proved that the optimal algorithm OPT (evict the page used furthest in the future) is unrealizable (requires future knowledge), and LRU is the closest achievable approximation to OPT.

Sleator and Tarjan (1985, "Amortized Efficiency of List Update and Paging Rules") further proved LRU's competitive ratio: for a cache with k page frames, LRU is k-competitive, meaning in the worst case, the number of page faults is at most k times that of OPT.

Linux Kernel's Approximate LRU

True LRU requires updating a linked list on every memory access—too expensive. The Linux kernel uses approximate LRU (Clock/Second-Chance algorithm):

• Pages have an accessed bit, set automatically by hardware when the page is accessed
• Periodically scan a circular list: if accessed=1, clear it (second chance); if accessed=0, evict
• Actual implementation is more complex: active list and inactive list (two-list approximate LRU/2)

This is why textbooks saying "the OS uses LRU" needs qualification—no system implements exact LRU; all use approximations.

38.12 LRU Implementation in Redis

Redis's maxmemory-policy supports multiple eviction strategies:

• volatile-lru: LRU among keys with TTL set
• allkeys-lru: LRU among all keys
• volatile-lfu: LFU (Redis 4.0+)
• allkeys-lfu: LFU (Redis 4.0+)

Redis's Approximate LRU Implementation

Redis does not maintain a true doubly linked list for every key. With millions or even billions of keys, the memory overhead and lock contention of maintaining a global list is unacceptable.

Redis's approach (improved by Salvatore Sanfilippo in Redis 3.0):

1. Each key's object header stores a 24-bit timestamp (lru field), recording the last access time (second precision)
2. During eviction, randomly sample N keys (default N=5, configurable via maxmemory-samples)
3. Evict the one with the oldest lru value from the N samples
4. Redis 3.0 introduced an eviction candidate pool: a pool of size 16, each sampling round adds "older" keys to the pool, evicting the oldest from the pool

Why is approximation sufficient? Salvatore's tests showed that with maxmemory-samples=10, approximate LRU's hit rate is virtually identical to exact LRU, but memory overhead drops from two pointers per key (16 bytes x key count) to 3 bytes per key (24-bit timestamp).

Redis's LFU Implementation

Redis 4.0's LFU uses a Morris counter (Morris, 1978, "Counting Large Numbers of Events in Small Registers") for probabilistic increment—8 bits represent a logarithmic approximation of frequency, preventing counter overflow for high-frequency keys. It also introduces time decay so that keys not accessed for long periods see their frequency decrease.

38.13 MySQL Buffer Pool's LRU Variant

MySQL InnoDB's Buffer Pool uses a modified LRU algorithm to solve two practical problems:

Problem 1: Read-Ahead Pollution

InnoDB pre-reads adjacent pages into the Buffer Pool. If pre-read pages go directly to the LRU list head, they push out genuinely hot data.

Solution: Midpoint Insertion

The list is divided into a "young" zone (hot end, default 5/8) and an "old" zone (cold end, 3/8). Newly read pages go to the head of the old zone first. Only after surviving in the old zone for longer than innodb_old_blocks_time (default 1 second) and being accessed again are they promoted to the young zone.

Problem 2: Full Table Scan Pollution

A single SELECT * FROM large_table reads all pages sequentially. With standard LRU, these pages would push all hot data out of the Buffer Pool.

The midpoint insertion strategy ensures full table scan pages only circulate in the old zone, never entering the young zone—because during a full table scan, each page is typically accessed only once, failing to meet the "survive for 1 second then be accessed again" promotion condition.

38.14 Cache Eviction Strategy Comparison

ARC Algorithm Detail (Megiddo & Modha, 2003, IBM Research)

ARC (Adaptive Replacement Cache) maintains four lists:

• T1: Pages recently accessed only once (similar to FIFO)
• T2: Pages recently accessed multiple times (similar to LRU)
• B1: Eviction history of T1 (ghost entries)
• B2: Eviction history of T2

Core idea: dynamically adjust T1 and T2 sizes based on B1 and B2 hit rates. If B1 is hit often (meaning single-access data gets accessed again later), grow T1; if B2 is hit often, grow T2.

ARC's elegance lies in requiring no manual parameter tuning—the algorithm self-adapts based on workload characteristics.

38.15 Theoretical Analysis of Cache Hit Rates

Stack Distance Model

Mattson et al. (1970, "Evaluation Techniques for Storage Hierarchies") proposed the stack distance model: for an LRU cache, the stack distance d of an access is defined as "how many distinct items have been accessed since the last access to this item." If cache capacity is C, the access hits if and only if d <= C.

Important corollary: LRU satisfies the inclusion property—everything in an LRU cache of capacity C is also in an LRU cache of capacity C+1. This means increasing cache size can never decrease hit rate.

However, LFU and ARC do not satisfy the inclusion property—increasing cache size can decrease hit rate under certain pathological workloads (though this rarely occurs in practice).

Level 4 · Edge Cases and Pitfalls

38.16 Interview Problem-Solving Framework for Design Questions

When encountering a "design a data structure" problem in interviews, use this five-step framework:

Step 1: Clarify Interfaces and Constraints

• Ask about time complexity requirements for each operation
• Ask about space constraints
• Ask about data scale (affects importance of constant factors)
• Ask about thread safety requirements

Step 2: Analyze Each Operation's Required "Atomic Capabilities"

Decompose each operation into fundamental capabilities:

• O(1) lookup → Hash table
• O(1) ordered insert/delete → Doubly linked list
• O(1) get max/min → Heap or auxiliary stack
• O(1) random access → Array
• O(log n) ordered traversal → Balanced BST

Step 3: Combine Data Structures

If no single structure satisfies all constraints, use multi-structure combination + cross-references:

• Hash table value stores linked list node pointer
• Linked list node stores key back to hash table
• Array indices and hash table cross-reference each other

Step 4: Handle Edge Cases

• Empty cache, full cache
• Inserting duplicate keys
• Removing non-existent keys
• Capacity 0 or 1 special cases

Step 5: Discuss Extensions

Interviewers typically follow up—prepare ahead:

• Concurrent-safe version
• Distributed version
• Persistent version

38.17 Concurrent-Safe LRU Cache

Problem: How do you ensure LRU Cache correctness in a multi-threaded environment?

Approach 1: Coarse-Grained Lock

import threading


class ConcurrentLRUCache:
    def __init__(self, capacity):
        self.cache = LRUCache(capacity)
        self.lock = threading.Lock()
    
    def get(self, key):
        with self.lock:
            return self.cache.get(key)
    
    def put(self, key, value):
        with self.lock:
            self.cache.put(key, value)

Pros: Simple and correct. Cons: Throughput limited, all operations serialized.

Approach 2: Segmented/Striped Locking

Divide the key space into N segments (typically N=16 or N=number of CPU cores), each with an independent lock and LRU list. hash(key) % N determines which segment a key belongs to.

class SegmentedLRUCache:
    def __init__(self, capacity, num_segments=16):
        self.num_segments = num_segments
        seg_capacity = max(1, capacity // num_segments)
        self.segments = [LRUCache(seg_capacity) for _ in range(num_segments)]
        self.locks = [threading.Lock() for _ in range(num_segments)]
    
    def _get_segment(self, key):
        return hash(key) % self.num_segments
    
    def get(self, key):
        seg = self._get_segment(key)
        with self.locks[seg]:
            return self.segments[seg].get(key)
    
    def put(self, key, value):
        seg = self._get_segment(key)
        with self.locks[seg]:
            self.segments[seg].put(key, value)

Java's ConcurrentHashMap in JDK 7 used this segmented locking idea. Caffeine (a high-performance Java cache library by Ben Manes) uses a more refined lock-free ring buffer + background write thread approach.

Approach 3: Read-Write Lock

If reads dominate, get only needs a read lock. But LRU's get modifies list order (move_to_head), so technically requires a write lock.

Workaround: Place access records in a lock-free ring buffer, with a background thread periodically batch-updating the list. This is Caffeine's approach—making get nearly lock-free, with list updates deferred asynchronously. The trade-off is that LRU's "most recently used" information has brief latency, but in high-concurrency scenarios, the throughput gain from this relaxation far outweighs the tiny precision loss.

38.18 LRU in Distributed Caches

Single-Machine LRU Limitations

Single-machine memory is limited (typically 64GB-512GB), unable to cache all hot data. Distributed caching is needed—multiple machines forming a cache cluster.

Consistent Hashing Sharding

Keys are assigned to different nodes via consistent hashing. Each node independently runs its own LRU Cache.

Issues:

• Node failure causes cache loss → cold start problem
• Scaling requires significant key migration
• Hot keys skew to a single node

Memcached's Slab Allocator + LRU

Memcached classifies by size (slab classes), each with an independent LRU list. This avoids memory fragmentation but may cause imbalance where small slab classes evict frequently while large ones sit idle.

Memcached 1.5 introduced "slab automove" and "slab reassign" mechanisms to mitigate this—dynamically reallocating memory pages between slab classes at runtime.

Redis Cluster Caching Strategy

Redis Cluster divides the key space into 16384 slots distributed across multiple master nodes. Each node independently executes its maxmemory-policy. The issue is that globally, node A might evict a somewhat warm key while node B has colder keys surviving—there is no global LRU view.

In practice, this "approximately good enough" philosophy pervades: exact global LRU requires cross-node coordination (distributed locks or consensus protocols), with unacceptable latency and complexity.

38.19 Common Interview Follow-Up Questions

Q: What if cached values are large (e.g., images)?

A: Do not store large objects directly in the LRU cache. Store only metadata and references (e.g., CDN URLs or object storage paths). The actual large objects live in CDN/S3/local SSD. LRU manages "which references are hot," not "which data is in memory."

Q: How do you combine LRU with TTL (time-to-live)?

A: Two strategies:

• Lazy deletion: On get, check if expired; if so, treat as miss and delete
• Background thread periodically scans and deletes expired keys (Redis's approach: every 100ms, randomly sample 20 keys with expiry set, delete expired ones; if expired ratio > 25%, continue sampling)

Q: How do you implement "auto-load from database if key is not in cache"?

A: This extends the Cache-Aside pattern. Add a loader callback to get:

def get(self, key, loader=None):
    if key in self.cache:
        return self.cache[key]
    if loader:
        value = loader(key)  # Load from DB
        self.put(key, value)
        return value
    return None

Google Guava and Caffeine's LoadingCache follows this design. The critical issue is cache stampede—many concurrent requests for the same missing key all penetrate to DB. Solutions include singleflight (Go standard library) or mutex + double-check.

38.20 Edge Case Summary for Design Problems

38.21 Design Data Structure vs System Design

"Design a data structure" and "system design" are fundamentally different interview categories:

But they intersect: when system design involves "what local caching strategy" or "how to implement a rate limiter," you need to demonstrate data structure-level knowledge. This chapter's content is precisely that intersection.

38.22 Production Cache Pattern Selection Decision Tree

Need caching?
├── Data fits in single-machine memory?
│   ├── Yes → Use in-process cache (HashMap + LRU/LFU)
│   │   ├── Read-heavy → LRU usually sufficient
│   │   ├── Full table scan risk → LRU-K or ARC
│   │   └── Frequency skew → LFU
│   └── No → Distributed cache
│       ├── Strong consistency needed → Redis (persistence + replication)
│       ├── Pure cache (loss acceptable) → Memcached
│       └── Complex data structures needed → Redis
├── Cache-database consistency?
│   ├── Tolerate brief inconsistency → Cache-Aside + TTL
│   ├── Need strong consistency → Write-Through or Write-Behind + version numbers
│   └── Eventual consistency OK → Subscribe binlog, async cache update
└── Cache penetration/stampede/avalanche?
    ├── Penetration (querying non-existent keys) → Bloom filter + null value cache
    ├── Stampede (hot key expires) → Mutex lock + logical expiry
    └── Avalanche (mass key expiration) → Random TTL + multi-level cache

Chapter Summary

Design data structure problems are fundamentally about requirement analysis + structure combination. Each fundamental data structure has operations it excels at and O(1) properties. When a single structure cannot meet all requirements, you must combine multiple structures and link them through pointers/indices.

Core patterns:

1. List all operations' time complexity requirements
2. For each operation, identify the fundamental structure that satisfies it
3. Use hash tables as "glue" to bind multiple structures together
4. Use sentinel nodes to simplify linked list boundary conditions
5. Use "swap to end" to achieve O(1) array deletion

LRU Cache is the cornerstone of all design problems—understanding the "hash table + doubly linked list" combination thinking, all other design problems are variants of the same idea. From an industry perspective, nobody uses exact LRU—approximation, segmentation, and asynchrony are the inevitable path of performance engineering.