Data structure design problems are among the most popular interview questions at top tech companies. This page provides complete, tested C++ implementations for LRU/LFU cache, Trie, time-based key-value store, and other classic design patterns. The key insight for most of these problems is combining two or more simple structures to achieve the required time complexity.

Design problems test your ability to compose data structures. The trick is almost always combining a hash map with another structure (linked list, heap, array) to get O(1) for multiple operations.

LRU Cache — hash map + doubly linked list Hash Map key=1 → node₁ key=2 → node₂ key=3 → node₃ O(1) lookup by key head (oldest) 1 2 3 tail (recent) Doubly linked list — O(1) insert/remove at any position get(3): map lookup → splice node to tail (mark recent) put(4): if full → evict head (oldest), insert at tail Both get and put are O(1)

Contents

Stack-based Design

When to use: “get min/max in O(1)”, “design a stack with extra operations”, or when you need to track additional state alongside the primary data.

Min Stack

Maintain a primary stack for data and an auxiliary stack to track the minimum value at each state.

class MinStack:
    def __init__(self) -> None:
        self.stk: list[int] = []
        self.min_stk: list[int] = []

    def push(self, val: int) -> None:
        self.stk.append(val)
        if not self.min_stk:
            self.min_stk.append(val)
        else:
            self.min_stk.append(min(self.min_stk[-1], val))

    def pop(self) -> None:
        self.stk.pop()
        self.min_stk.pop()

    def top(self) -> int:
        return self.stk[-1]

    def getMin(self) -> int:
        return self.min_stk[-1]
ID Title Link Solution
155 Min Stack Link Solution

LRU Cache

When to use: “least recently used”, “design a cache with O(1) get and put”, or any eviction policy based on access recency.

Least Recently Used cache using hash map + doubly linked list.

from collections import OrderedDict


class LRUCache:
    """LRU via OrderedDict (move_to_end on access)."""

    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.cache: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

Thread-Safe LRU Cache

Thread-safe version using mutex for concurrent access.

import threading
from collections import OrderedDict


class ThreadSafeLRUCache:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.cache: OrderedDict[int, int] = OrderedDict()
        self._lock = threading.Lock()

    def get(self, key: int) -> int:
        with self._lock:
            if key not in self.cache:
                return -1
            self.cache.move_to_end(key)
            return self.cache[key]

    def put(self, key: int, value: int) -> None:
        with self._lock:
            if key in self.cache:
                self.cache[key] = value
                self.cache.move_to_end(key)
                return
            self.cache[key] = value
            if len(self.cache) > self.capacity:
                self.cache.popitem(last=False)

    def size(self) -> int:
        with self._lock:
            return len(self.cache)
ID Title Link Solution
146 LRU Cache Link Solution

LFU Cache

When to use: “least frequently used”, “evict the element used fewest times”, or cache designs where frequency matters more than recency.

Least Frequently Used cache.

from collections import defaultdict, OrderedDict


class LFUCache:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.min_freq = 0
        self.key_val: dict[int, int] = {}
        self.key_freq: dict[int, int] = {}
        self.freq_keys: dict[int, OrderedDict[int, None]] = defaultdict(OrderedDict)

    def _touch(self, key: int) -> None:
        f = self.key_freq[key]
        self.freq_keys[f].pop(key)
        if not self.freq_keys[f] and f == self.min_freq:
            self.min_freq += 1
        f += 1
        self.key_freq[key] = f
        self.freq_keys[f][key] = None

    def get(self, key: int) -> int:
        if key not in self.key_val:
            return -1
        self._touch(key)
        return self.key_val[key]

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.key_val:
            self.key_val[key] = value
            self._touch(key)
            return
        if len(self.key_val) >= self.capacity:
            k, _ = self.freq_keys[self.min_freq].popitem(last=False)
            del self.key_val[k]
            del self.key_freq[k]
        self.key_val[key] = value
        self.key_freq[key] = 1
        self.freq_keys[1][key] = None
        self.min_freq = 1
ID Title Link Solution
460 LFU Cache Link Solution

Trie

When to use: “prefix search”, “autocomplete”, “word dictionary with wildcards”, or any problem requiring efficient prefix lookups over a set of strings.

Prefix tree for efficient string operations.

class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.is_end = False


class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True
ID Title Link Solution
208 Implement Trie (Prefix Tree) Link -
211 Design Add and Search Words Data Structure Link -

Time-based Key-Value Store

When to use: “get value at timestamp”, “versioned storage”, or when you need to retrieve the most recent value at or before a given time.

import bisect
from collections import defaultdict


class TimeMap:
    def __init__(self) -> None:
        self.store: dict[str, list[tuple[int, str]]] = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        pairs = self.store.get(key)
        if not pairs:
            return ""
        i = bisect.bisect_right(pairs, (timestamp, chr(0x10FFFF))) - 1
        if i < 0:
            return ""
        return pairs[i][1]
ID Title Link Solution
981 Time Based Key-Value Store Link -
362 Design Hit Counter Link Solution
1146 Snapshot Array Link Solution

Design Patterns

When to use: “random with weight”, “design tic-tac-toe”, “iterator”, or other custom data structure problems that combine multiple techniques.

Random Pick with Weight

import bisect
import random


class Solution:
    def __init__(self, w: list[int]) -> None:
        self.prefix: list[int] = []
        s = 0
        for x in w:
            s += x
            self.prefix.append(s)

    def pickIndex(self) -> int:
        t = random.randint(1, self.prefix[-1])
        return bisect.bisect_left(self.prefix, t)

Design Tic-Tac-Toe

class TicTacToe:
    def __init__(self, n: int) -> None:
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diag = 0
        self.anti = 0

    def move(self, row: int, col: int, player: int) -> int:
        add = 1 if player == 1 else -1
        self.rows[row] += add
        self.cols[col] += add
        if row == col:
            self.diag += add
        if row + col == self.n - 1:
            self.anti += add
        n = self.n
        if (
            abs(self.rows[row]) == n
            or abs(self.cols[col]) == n
            or abs(self.diag) == n
            or abs(self.anti) == n
        ):
            return player
        return 0
ID Title Link Solution
528 Random Pick with Weight Link Solution
348 Design Tic-Tac-Toe Link Solution
1275 Find Winner on a Tic Tac Toe Game Link Solution
398 Random Pick Index Link Solution
2043 Simple Bank System Link Solution
281 Zigzag Iterator Link Solution
1206 Design Skiplist Link Solution
341 Flatten Nested List Iterator Link Solution
1115 Print FooBar Alternately Link Solution
1188 Design Bounded Blocking Queue Link Solution

Summary

Pattern Signal Phrases Structures Used
Min Stack “min in O(1)” Two stacks
LRU Cache “least recently used” Hash map + doubly linked list
LFU Cache “least frequently used” Hash map + frequency buckets
Trie “prefix search”, “autocomplete” Tree of character nodes
Time-based KV “get value at timestamp” Hash map + binary search

More templates