Data Structure Design Problems

"Design a data structure that supports these operations, each in $O(1)$" is a popular interview format. There is no new algorithm to learn. You combine the structures from earlier chapters, hash maps, linked lists, heaps, stacks and arrays, so that each operation has the cost the problem demands. The method is to list the required operations and their target costs, then ask which structure gives each operation, and how to glue them so that they stay consistent.

1. The method

1. Write down every operation and its required complexity. For example: get and put in $O(1)$.
2. Find the structure that gives each in isolation. Lookup by key: hash map. Order by recency: doubly linked list. Minimum: heap or an extra stack. Random access: array.
3. Combine them so they reference each other. The hash map often stores pointers to nodes in the other structure, so a lookup in one gives you direct access in the other.
4. State the invariant that keeps them consistent after every operation.
5. Check every operation against the invariant, especially edge cases (empty, one element, capacity reached).

2. LRU cache

get(key) and put(key, value) in $O(1)$, evicting the least recently used entry when full. A hash map gives $O(1)$ lookup, and a doubly linked list ordered by recency gives $O(1)$ move-to-front and eviction. The map points to list nodes.

class Node:
    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: no edge cases at the ends
        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 _push_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._push_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._push_front(node)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]                              # the node stores its key for this reason

c = LRUCache(2)
c.put(1, 1); c.put(2, 2)
assert c.get(1) == 1
c.put(3, 3)
assert c.get(2) == -1
c.put(4, 4)
assert (c.get(1), c.get(3), c.get(4)) == (-1, 3, 4)

The detail interviewers watch for: the node stores its key, because when evicting the tail you must delete the matching entry from the map. With Python's OrderedDict the same cache is a few lines (move_to_end, popitem(last=False)), and it is worth mentioning, though many interviewers ask for the manual version.

3. LFU cache

Evict the least frequently used key, breaking ties by least recent use, with $O(1)$ operations. Keep a map from key to (value, frequency), and for each frequency an ordered collection of keys (an OrderedDict serves as an LRU list per frequency), plus the current minimum frequency.

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.vals = {}                                   # key -> value
        self.freq = {}                                   # key -> use count
        self.buckets = defaultdict(OrderedDict)          # count -> keys in recency order
        self.min_freq = 0

    def _touch(self, key):
        f = self.freq[key]
        del self.buckets[f][key]
        if not self.buckets[f] and self.min_freq == f:
            self.min_freq += 1                           # the lowest bucket emptied
        self.freq[key] = f + 1
        self.buckets[f + 1][key] = None

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

    def put(self, key, value):
        if self.cap == 0:
            return
        if key in self.vals:
            self.vals[key] = value
            self._touch(key)
            return
        if len(self.vals) >= self.cap:
            evict, _ = self.buckets[self.min_freq].popitem(last=False)   # least recent among least frequent
            del self.vals[evict], self.freq[evict]
        self.vals[key] = value
        self.freq[key] = 1
        self.buckets[1][key] = None
        self.min_freq = 1

lfu = LFUCache(2)
lfu.put(1, 1); lfu.put(2, 2)
assert lfu.get(1) == 1
lfu.put(3, 3)                                            # evicts key 2 (frequency 1)
assert lfu.get(2) == -1 and lfu.get(3) == 3
lfu.put(4, 4)                                            # keys 1 and 3 both have frequency 2: evict 1
assert lfu.get(1) == -1 and lfu.get(3) == 3 and lfu.get(4) == 4

The key idea is min_freq: after inserting a new key it is 1, and after touching a key it only increases when its old bucket empties.

4. Min stack and max stack

Retrieve the minimum in $O(1)$ by storing, with each element, the minimum of everything beneath it.

class MinStack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        self.stack.append((x, min(x, self.stack[-1][1]) if self.stack else x))

    def pop(self):
        self.stack.pop()

    def top(self):
        return self.stack[-1][0]

    def get_min(self):
        return self.stack[-1][1]

m = MinStack()
for v in (3, 1, 2):
    m.push(v)
assert m.get_min() == 1
m.pop(); m.pop()
assert m.get_min() == 3 and m.top() == 3

Max stack with popMax needs more: a stack plus a heap with lazy deletion, or a doubly linked list plus a sorted structure. Mention the trade-off between simplicity and the extra operation.

5. Randomised set: insert, delete and random in $O(1)$

insert(x), remove(x) and get_random() each in $O(1)$ average. A list gives uniform random access, a hash map from value to index gives $O(1)$ lookup. To delete in $O(1)$, swap the element with the last one and pop.

import random

class RandomizedSet:
    def __init__(self):
        self.items = []
        self.index = {}                                  # value -> position in items

    def insert(self, val):
        if val in self.index:
            return False
        self.index[val] = len(self.items)
        self.items.append(val)
        return True

    def remove(self, val):
        if val not in self.index:
            return False
        i, last = self.index[val], self.items[-1]
        self.items[i] = last                             # move the last element into the gap
        self.index[last] = i
        self.items.pop()
        del self.index[val]                              # delete after updating, in case val == last
        return True

    def get_random(self):
        return random.choice(self.items)

rs = RandomizedSet()
assert rs.insert(1) and not rs.insert(1) and rs.insert(2)
assert rs.remove(1) and not rs.remove(1)
assert rs.get_random() == 2
assert rs.insert(3) and rs.remove(3) and rs.items == [2]

The order of the last three lines in remove matters when val is the last element, which is why the deletion from the map comes last.

6. Time-based key-value store

set(key, value, timestamp) and get(key, timestamp) returning the latest value set at or before that timestamp. Timestamps for a key arrive in increasing order, so each key keeps a sorted list, and get uses binary search.

import bisect

class TimeMap:
    def __init__(self):
        self.times = defaultdict(list)
        self.values = defaultdict(list)

    def set(self, key, value, timestamp):
        self.times[key].append(timestamp)
        self.values[key].append(value)

    def get(self, key, timestamp):
        i = bisect.bisect_right(self.times[key], timestamp)
        return self.values[key][i - 1] if i else ""

tm = TimeMap()
tm.set("a", "x", 1); tm.set("a", "y", 4)
assert tm.get("a", 3) == "x" and tm.get("a", 4) == "y" and tm.get("a", 0) == ""
assert tm.get("zzz", 5) == ""

7. Hit counter and rate limiting

Count events in the last 5 minutes. A queue of timestamps, with old ones dropped from the front, gives $O(1)$ amortised updates. For very high rates, a fixed array of buckets (one per second, 300 total) in a ring gives constant memory.

from collections import deque

class HitCounter:
    def __init__(self):
        self.hits = deque()

    def hit(self, timestamp):
        self.hits.append(timestamp)

    def get_hits(self, timestamp):
        while self.hits and self.hits[0] <= timestamp - 300:     # drop hits older than 5 minutes
            self.hits.popleft()
        return len(self.hits)

hc = HitCounter()
for t in (1, 2, 3):
    hc.hit(t)
assert hc.get_hits(4) == 3
hc.hit(300)
assert hc.get_hits(300) == 4                                      # the window is (0, 300], so all four count
assert hc.get_hits(301) == 3                                      # the hit at time 1 has expired
assert hc.get_hits(302) == 2

This connects to the system design chapter on rate limiting, where the same structures appear at a larger scale.

8. Design with a heap: Twitter timeline, task scheduler

News feed: post(user, tweet), follow, unfollow, and get_feed(user) returning the 10 most recent tweets from the user and those they follow. Store each user's tweets as a list with a global timestamp, and merge the followees' lists with a heap (the merge-$k$-sorted-lists pattern), taking the top 10.

import heapq

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)                  # user -> [(time, tweet_id)]
        self.following = defaultdict(set)

    def post_tweet(self, user, tweet_id):
        self.time += 1
        self.tweets[user].append((self.time, tweet_id))

    def get_news_feed(self, user):
        heap = []
        for u in self.following[user] | {user}:
            if self.tweets[u]:
                t, tid = self.tweets[u][-1]
                heapq.heappush(heap, (-t, tid, u, len(self.tweets[u]) - 1))
        feed = []
        while heap and len(feed) < 10:
            _, tid, u, i = heapq.heappop(heap)
            feed.append(tid)
            if i > 0:
                t, nxt = self.tweets[u][i - 1]
                heapq.heappush(heap, (-t, nxt, u, i - 1))
        return feed

    def follow(self, follower, followee):
        self.following[follower].add(followee)

    def unfollow(self, follower, followee):
        self.following[follower].discard(followee)

tw = Twitter()
tw.post_tweet(1, 5)
assert tw.get_news_feed(1) == [5]
tw.follow(1, 2); tw.post_tweet(2, 6)
assert tw.get_news_feed(1) == [6, 5]
tw.unfollow(1, 2)
assert tw.get_news_feed(1) == [5]

9. Design with a trie or a two-structure combination

Autocomplete system (trie plus a ranking rule), word dictionary with wildcards (trie with DFS on .), magic dictionary and map sum use a trie as the core. Range sum with updates uses a Fenwick tree or segment tree (the next chapter). Snapshot arrays store per-index history and binary search by snapshot id. Iterators (flatten nested list, peeking iterator, binary search tree iterator) maintain an explicit stack of the traversal state so next and has_next take amortised $O(1)$.

class BSTIterator:
    """In-order iterator with O(h) memory; next() is amortised O(1)."""
    def __init__(self, root):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self):
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val

    def has_next(self):
        return bool(self.stack)

class T:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

it = BSTIterator(T(7, T(3), T(15, T(9), T(20))))
out = []
while it.has_next():
    out.append(it.next())
assert out == [3, 7, 9, 15, 20]

10. How to present a design answer

1. Clarify the operations, their frequencies and the target complexities, plus the constraints (capacity, thread safety, whether keys are integers).
2. State the structures and why each exists: "the map gives lookup, the list gives order".
3. Describe the invariant that holds after each operation.
4. Walk through one example showing each operation.
5. Handle edge cases aloud: empty, capacity zero, duplicate keys, deleting a missing key.
6. Mention thread safety if relevant: a lock around the operations, or finer-grained locking, with the trade-off. Many interviewers ask this as a follow-up for LRU.
7. Analyse complexity of each operation and the space.

11. Common mistakes

• Storing values instead of node references in the map, so you cannot reach the list node in $O(1)$.
• Forgetting to update both structures on every operation, leaving them inconsistent.
• Leaving out sentinel nodes, producing special cases at the head and tail.
• Deleting from a list in $O(n)$ where a swap-with-last gives $O(1)$ (when order does not matter).
• Off-by-one errors in capacity checks (> versus >=).
• Ignoring ties (LFU's least recent among equal frequencies).
• Not handling re-insertion of an existing key as an update plus a recency refresh.
• Not asking about thread safety when the design is meant for concurrent use.

12. Practice set

1. LRU cache, LFU cache.
2. Min stack, max stack, stack with get_middle, queue using stacks, stack using queues.
3. Insert delete getRandom $O(1)$, with duplicates allowed.
4. Time-based key-value store, snapshot array, logger rate limiter, hit counter.
5. Design Twitter, design a leaderboard.
6. Implement trie, design add and search words, design search autocomplete.
7. BST iterator, flatten nested list iterator, peeking iterator, zigzag iterator.
8. Moving average from a data stream, find median from a data stream.
9. Design a parking lot, design an elevator (object-oriented design, a different skill).
10. Design a hash map and a hash set from scratch (buckets, resizing, collision handling).