Data Structure Design
On this page
"Design a class that supports these operations" is its own kind of coding question. LRU Cache is the famous one, and many companies now run whole rounds this way: build a small key-value store, a bank, a rate limiter or a spreadsheet, then add a new requirement every fifteen minutes. No single algorithm is the answer. The skill is choosing a few structures that together make every operation fast, and writing code that survives the next requirement.
When to recognise it
- The prompt is a class with several methods:
get,put,set,delete,hit,transfer. - It names a target cost for each operation ("all in O(1)", "O(log n) per call").
- It arrives in levels: "part 2: keys now expire", "part 3: support transactions", "part 4: undo".
- It looks like system design (a cache, a rate limiter, a file system) but you are asked to write the code, in memory, on one machine.
Step 1: list the operations, then pick a structure for each need
Write every method with the cost you want. For each one, ask which structure gives that cost. When no single structure covers all of them, combine two and keep them in sync.

| Need | Structure |
|---|---|
| Find by key | hash map |
| Oldest / newest first | linked list, deque or queue |
| Smallest / largest first | heap, or a sorted structure if items change |
| Value at a time or version | list of (time, value) + binary search |
| Random element in O(1) | array + map from value to index |
| Fixed capacity, wrap around | array + head index + size |
| Paths or prefixes | trie (tree of dictionaries) |
from collections import OrderedDict
class LRUCache:
"""Hash map for lookup + an ordered structure for recency (OrderedDict is both)."""
def __init__(self, capacity):
self.cap = capacity
self.data = OrderedDict()
def get(self, key):
if key not in self.data:
return -1
self.data.move_to_end(key) # now the most recently used
return self.data[key]
def put(self, key, value):
self.data[key] = value
self.data.move_to_end(key)
if len(self.data) > self.cap:
self.data.popitem(last=False) # evict the least recently used
In the interview, say that OrderedDict is a hash map plus a doubly linked list, and be ready to write the list yourself: LRU Cache shows both.
Step 2: one source of truth
When two structures describe the same data, every write must update both, or they drift apart. Keep the number of stored fields small and compute the rest. A circular queue stores head and size and computes the tail, so "full" and "empty" can never disagree.
class CircularQueue:
"""Fixed array + head index + size; the tail is computed, so there is one source of truth."""
def __init__(self, k):
self.buf = [None] * k
self.head = 0
self.size = 0
def push(self, x):
if self.size == len(self.buf):
return False
self.buf[(self.head + self.size) % len(self.buf)] = x
self.size += 1
return True
def pop(self):
if self.size == 0:
return None
x = self.buf[self.head]
self.head = (self.head + 1) % len(self.buf)
self.size -= 1
return x
Step 3: build for the next level
Levelled rounds reward a small core that every method goes through. If all reads pass through one helper, adding expiry, permissions or history later means changing that helper, not every method.

class KVStore:
"""Level 1 core plus level 2 (TTL). Every read goes through _live, so expiry lives in one place."""
def __init__(self):
self.data = {} # key -> (value, expires_at or None)
def _live(self, key, now):
item = self.data.get(key)
if item is None:
return None
value, exp = item
if exp is not None and now >= exp:
del self.data[key] # lazy expiry: clean up on read
return None
return value
def set(self, key, value, now, ttl=None):
self.data[key] = (value, None if ttl is None else now + ttl)
def get(self, key, now):
return self._live(key, now)
def delete(self, key, now):
return self.data.pop(key, None) is not None
Passing now in, instead of reading the clock inside, makes the class easy to test and is what most levelled prompts expect.
Common bugs
- Two structures out of sync: deleting from the map but not the list, or the reverse.
- Forgetting the update case:
puton an existing key must not count as a new item or trigger an eviction. - Off-by-one at capacity: evict when the size goes above capacity, after inserting, or at capacity, before inserting. Pick one.
- Expired data still counted in sizes, scans or prefix queries.
- Rewriting the class at each level instead of extending a shared helper.
Say this in the interview
- "Let me list each operation with the cost I want, then pick structures."
- "The map gives me lookup, the list gives me order; every write updates both."
- "I'll keep reads in one helper, so when expiry or transactions come next, only that helper changes."
Problems for this pattern
- LRU Cache: hash map + doubly linked list.
- Design Circular Queue: array + head + size.
- Design Tic-Tac-Toe: row, column and diagonal counters instead of scanning the board.
- Implement a Rate Limiter: a queue of timestamps or a token bucket per user.
- Resumable Iterator: keep the position as state you can save and restore.
- Implement an In-Memory Key-Value Store: a levelled round with TTL, transactions and snapshots.
- Simple Bank System: accounts in a map, validation before every change.
- LFU Cache: a list per frequency plus the minimum frequency.
- Design Spreadsheet: cells, formulas and a dependency graph.
Several design problems sit with the pattern that does the real work: Min Stack (Stacks), Insert Delete GetRandom O(1) and Logger Rate Limiter (Hash Maps), Time Based Key-Value Store (Binary Search), Design Hit Counter (Sliding Window), Find Median from Data Stream (Heaps), Design In-Memory File System (Tries) and Design Memory Allocator (Intervals).
Related
Hash Maps · Linked Lists · Stacks and Queues · Matrix and Simulation