Data Structure Design Problems
Combining structures to hit target complexities — LRU and LFU caches, O(1) randomized sets, iterators, time-based stores, rate limiters and more.
How to approach a design problem
- List the operations and the required complexity of each (often O(1) or O(log n)).
- For each operation, ask which structure gives that complexity:
- lookup by key → hash map
- order by recency / insertion → linked list or deque
- order by value / priority → heap or balanced BST
- random access by index → array
- Combine structures and keep them consistent: every mutation updates all of them.
- Walk through each operation on a small example and check edge cases (capacity 0/1, duplicate keys, empty state).
LRU cache
Get and put in O(1); evict the least recently used key when full.
- Hash map: key → node.
- Doubly linked list: most recent at the head, least recent at the tail.
class Node:
__slots__ = ("key", "val", "prev", "next")
def __init__(self, key=0, val=0):
self.key, self.val = key, val
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.map = {}
self.head, self.tail = Node(), Node() # sentinels
self.head.next, self.tail.prev = self.tail, self.head
def _remove(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _add_front(self, node):
node.prev, node.next = self.head, self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_front(node)
return node.val
def put(self, key, value):
if key in self.map:
self._remove(self.map[key])
node = Node(key, value)
self.map[key] = node
self._add_front(node)
if len(self.map) > self.cap:
lru = self.tail.prev
self._remove(lru)
del self.map[lru.key] # why nodes store their key
class LRUCache {
int cap;
list<pair<int,int>> items; // front = most recent
unordered_map<int, list<pair<int,int>>::iterator> pos;
public:
LRUCache(int capacity) : cap(capacity) {}
int get(int key) {
auto it = pos.find(key);
if (it == pos.end()) return -1;
items.splice(items.begin(), items, it->second); // O(1) move to front
return it->second->second;
}
void put(int key, int value) {
auto it = pos.find(key);
if (it != pos.end()) {
it->second->second = value;
items.splice(items.begin(), items, it->second);
return;
}
items.emplace_front(key, value);
pos[key] = items.begin();
if ((int)items.size() > cap) {
pos.erase(items.back().first);
items.pop_back();
}
}
};
LFU cache
Evict the least frequently used key; ties broken by least recently used.
key → (value, freq)freq → OrderedDict of keys(LRU order within each frequency)min_freq— the smallest frequency with any keys (it only resets to 1 on insert, or increments when its bucket empties during a touch).
Python
from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity):
self.cap = capacity
self.kv = {} # key -> [value, freq]
self.buckets = defaultdict(OrderedDict) # freq -> keys in LRU order
self.min_freq = 0
def _touch(self, key):
val, f = self.kv[key]
del self.buckets[f][key]
if not self.buckets[f]:
del self.buckets[f]
if self.min_freq == f:
self.min_freq += 1
self.kv[key][1] = f + 1
self.buckets[f + 1][key] = None
def get(self, key):
if key not in self.kv:
return -1
self._touch(key)
return self.kv[key][0]
def put(self, key, value):
if self.cap == 0:
return
if key in self.kv:
self.kv[key][0] = value
self._touch(key)
return
if len(self.kv) == self.cap:
evict, _ = self.buckets[self.min_freq].popitem(last=False)
if not self.buckets[self.min_freq]:
del self.buckets[self.min_freq]
del self.kv[evict]
self.kv[key] = [value, 1]
self.buckets[1][key] = None
self.min_freq = 1
Insert / delete / getRandom in O(1)
- Array holds the values (random index → O(1) random pick).
- Map value → index in the array.
- Delete by swapping the target with the last element, updating the moved element's index, then popping.
Python
import random
class RandomizedSet:
def __init__(self):
self.vals, self.idx = [], {}
def insert(self, val):
if val in self.idx:
return False
self.idx[val] = len(self.vals)
self.vals.append(val)
return True
def remove(self, val):
if val not in self.idx:
return False
i, last = self.idx[val], self.vals[-1]
self.vals[i], self.idx[last] = last, i # move last into the hole
self.vals.pop()
del self.idx[val]
return True
def getRandom(self):
return random.choice(self.vals)
With duplicates allowed, map each value to a set of indices.
Versioned / time-based data
Store, per key, a list of (time, value) appended in increasing time, and binary search on reads.
Python
from bisect import bisect_right
from collections import defaultdict
class TimeMap:
def __init__(self):
self.times = defaultdict(list)
self.values = defaultdict(list)
def set(self, key, value, timestamp): # timestamps arrive increasing
self.times[key].append(timestamp)
self.values[key].append(value)
def get(self, key, timestamp):
i = bisect_right(self.times[key], timestamp)
return self.values[key][i - 1] if i else ""
Snapshot Array is the same idea keyed by index and snapshot id.
Iterators
Iterators should do lazy work: advance only as far as needed in hasNext, and keep O(depth) state rather than flattening everything up front.
Python
class NestedIterator:
def __init__(self, nested_list):
self.stack = [iter(nested_list)]
self.peeked = None
def hasNext(self):
if self.peeked is not None:
return True
while self.stack:
try:
x = next(self.stack[-1])
except StopIteration:
self.stack.pop()
continue
if x.isInteger():
self.peeked = x.getInteger()
return True
self.stack.append(iter(x.getList()))
return False
def next(self):
self.hasNext() # fills peeked if the caller skipped hasNext
v, self.peeked = self.peeked, None
return v
hasNext buffers the next integer in peeked, so calling it repeatedly is safe and next never skips a value.
Rate limiting and sliding counters
- Hit counter / logger: queue of timestamps; drop those outside the window on each call. For huge volumes, use a circular array of 300 buckets
(time, count). - Token bucket: track tokens and last refill time; refill
rate × elapsedlazily on each request.
Aggregates with a sorted structure
- Stock Price Fluctuation: map timestamp → price, plus a sorted multiset (or two lazy-deletion heaps) of prices for current max/min.
- Design a Leaderboard / Exam Room / Seat Manager: balanced BST or heap depending on whether you need arbitrary deletion.
Checklist for design interviews
- State each operation's complexity before coding.
- Keep all structures consistent on every mutation (the most common bug).
- Sentinels for linked lists.
- Handle capacity 0, updates to existing keys, and removing missing keys.
- Mention thread safety / persistence only if asked — it's a DSA problem, not system design.
Practice problems
Ordered roughly from warm-up to hard. Try each one for 25–40 minutes before peeking at the key idea; if you needed the hint, mark it “review” and redo it in a few days.
Easy
Medium
Medium
Medium
Medium
Medium
Hard
Click the box to cycle: solved ✓ → needs review ↺ → not started. Links open LeetCode.