CodeVerse Creatives
Esc
DSA in C++ Syllabus / Module 14 · Design Problems / Week 17

Week 17: Design Problems — Building Custom Data Structures

Every week so far has asked "solve this problem using a data structure." Design problems flip the question: "build a data structure with these exact operations and complexity guarantees." They're one of the most common interview categories precisely because they can't be solved by pattern-matching to a known algorithm name — you have to reason from the required operations back to a structure that supports all of them at the required speed. This week builds four classics: an LRU cache combining a hash map with a doubly linked list, a stack that reports its minimum in O(1), a hash map built from array buckets, and a simplified Twitter feed that merges per-user post streams with the heap from Week 11.

Module 14 of 17 Week 17 of 20 ~3–4 Hours Hands-on Exercise Included

By the end of this week, you'll be able to

  • Build an LRU cache with O(1) get and put by combining a hash map with a doubly linked list
  • Design a stack that supports O(1) minimum retrieval and a hash map from array buckets
  • Reason from a set of required operations to the right combination of structures, instead of starting from an algorithm name
1 LRU Cache 2 Min Stack 3 Design a HashMap 4 Design Twitter 5 Exercise 6 Knowledge Check

1. LRU Cache

An LRU (least-recently-used) cache needs get(key) and put(key, value) in O(1), evicting the least-recently-used entry whenever a put would exceed capacity. A hash map alone gives O(1) lookup but no sense of "order of use." A linked list alone gives O(1) reordering but O(n) lookup. Combining them — a hash map from key to a node in a doubly linked list, kept in most-to-least-recently-used order — gives both guarantees at once.

lru_cache.cpp
#include <unordered_map>
using namespace std;

class LRUCache {
public:
    LRUCache(int capacity) : cap(capacity) {
        head = new Node(0, 0);   // dummy head: head->next is the most recently used
        tail = new Node(0, 0);   // dummy tail: tail->prev is the least recently used
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return -1;
        moveToFront(it->second);
        return it->second->value;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            it->second->value = value;
            moveToFront(it->second);
            return;
        }
        if ((int)map.size() == cap) {
            Node* lru = tail->prev;              // least recently used
            remove(lru);
            map.erase(lru->key);
            delete lru;
        }
        Node* node = new Node(key, value);
        insertAtFront(node);
        map[key] = node;
    }

private:
    struct Node {
        int key, value;
        Node *prev = nullptr, *next = nullptr;
        Node(int k, int v) : key(k), value(v) {}
    };

    int cap;
    Node *head, *tail;
    unordered_map<int, Node*> map;

    void remove(Node* n) {
        n->prev->next = n->next;
        n->next->prev = n->prev;
    }

    void insertAtFront(Node* n) {
        n->next = head->next;
        n->prev = head;
        head->next->prev = n;
        head->next = n;
    }

    void moveToFront(Node* n) {
        remove(n);
        insertAtFront(n);
    }
};

Both dummy head and tail nodes exist for the same reason Week 15's capstone tokenizer used an END sentinel: they let insertAtFront and remove operate without ever checking for a null neighbor, since every real node always has a valid prev and next to link against. Every operation the map or list performs — find, remove, insertAtFront — is O(1), so get and put both stay O(1) overall.

The map stores pointers, not values

The whole design hinges on map holding Node* rather than the value directly — that's what lets get jump straight to the right list node in O(1) and re-splice it, instead of having to search the list for it. Any design-a-cache variant (LFU, TinyLFU, a fixed-size FIFO cache) starts from this same "hash map of pointers into an ordered structure" template.

2. Min Stack: O(1) getMin

A min stack needs push, pop, top, and getMin all in O(1). Recomputing the minimum on every getMin call would be O(n); instead, maintain a second stack that tracks the minimum seen so far at each depth, pushed and popped in lockstep with the main stack.

min_stack.cpp
#include <stack>
#include <climits>
using namespace std;

class MinStack {
public:
    void push(int val) {
        data.push(val);
        // minStack's top is always "the minimum of everything currently on `data`"
        minStack.push(minStack.empty() ? val : min(val, minStack.top()));
    }

    void pop() {
        data.pop();
        minStack.pop();
    }

    int top() { return data.top(); }
    int getMin() { return minStack.top(); }

private:
    stack<int> data;
    stack<int> minStack;
};

The invariant that makes this correct: after every push, minStack.top() equals the minimum of every element currently in data, not just the newest one. Because both stacks grow and shrink together, popping an element from data also pops the minimum that was computed including that element — automatically restoring minStack.top() to the correct minimum of what remains, with no recomputation needed.

The "auxiliary structure in lockstep" pattern

Min stack is the simplest example of a broader design move: when you need O(1) access to an aggregate (min, max, running sum) over whatever's currently in a structure, maintain a second structure that tracks that aggregate and mutates in lockstep with the first. It generalizes directly to a max stack, and with more work, to a queue that supports O(1) amortized minimum via two stacks.

3. Design a HashMap from Scratch

Implementing your own hash map — without std::unordered_map — forces you to make the trade-off a real hash table hides behind its interface: an array of fixed size, with a hash function mapping keys to buckets, and a collision-resolution strategy for when two keys land in the same bucket. Separate chaining (each bucket holds a small list of entries) is the simplest correct strategy.

my_hashmap.cpp
#include <vector>
#include <list>
#include <utility>
using namespace std;

class MyHashMap {
public:
    MyHashMap() : buckets(INITIAL_SIZE) {}

    void put(int key, int value) {
        auto& bucket = buckets[hashOf(key)];
        for (auto& [k, v] : bucket) {
            if (k == key) { v = value; return; }   // update existing key
        }
        bucket.emplace_back(key, value);
        count++;
        if (count > (int)buckets.size() * LOAD_FACTOR) resize();
    }

    int get(int key) {
        auto& bucket = buckets[hashOf(key)];
        for (auto& [k, v] : bucket) {
            if (k == key) return v;
        }
        return -1;
    }

    void remove(int key) {
        auto& bucket = buckets[hashOf(key)];
        bucket.remove_if([key](const pair<int,int>& p) { return p.first == key; });
    }

private:
    static const int INITIAL_SIZE = 16;
    static constexpr double LOAD_FACTOR = 0.75;

    vector<list<pair<int,int>>> buckets;
    int count = 0;

    int hashOf(int key) const {
        return (key % (int)buckets.size() + (int)buckets.size()) % (int)buckets.size();
    }

    void resize() {
        vector<list<pair<int,int>>> old = move(buckets);
        buckets.assign(old.size() * 2, {});   // double the bucket count
        for (auto& bucket : old) {
            for (auto& [k, v] : bucket) {
                buckets[hashOf(k)].emplace_back(k, v);   // rehash into the new bucket count
            }
        }
    }
};

get, put, and remove are all O(1) on average, degrading to O(n) only in the worst case where every key collides into the same bucket. The LOAD_FACTOR threshold and resize are what keep the average case true in practice: as more keys get inserted, each bucket's list would otherwise grow linearly, turning every operation into a linear scan — doubling the bucket count and rehashing keeps the average bucket length bounded by a small constant.

Say "amortized" and "worst case" explicitly

A common follow-up is "what's the actual worst-case complexity of get?" The honest answer is O(n) — a pathological key set or a broken hash function can put every key in one bucket. Naming that worst case unprompted, alongside the average-case O(1) the load factor is designed to maintain, signals you understand the structure rather than having memorized "hash maps are O(1)."

4. Design Twitter: Merging Per-User Feeds with a Heap

A simplified Twitter needs postTweet(userId, tweetId), follow/unfollow, and getNewsFeed(userId) returning the 10 most recent tweet IDs across the user and everyone they follow. Each user's own tweets are already in recency order by construction (append-only); the real problem is merging several already-sorted lists (one per followed user) into one globally sorted result — exactly the k-sorted-lists merge Week 11's heap section previewed with the top-K pattern.

design_twitter.cpp
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;

class Twitter {
public:
    void postTweet(int userId, int tweetId) {
        tweets[userId].push_back({timestamp++, tweetId});
    }

    void follow(int followerId, int followeeId) {
        if (followerId != followeeId) following[followerId].insert(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        following[followerId].erase(followeeId);
    }

    vector<int> getNewsFeed(int userId) {
        // Max-heap of {timestamp, tweetId, sourceUserId, indexInThatUsersList}
        priority_queue<tuple<int,int,int,int>> heap;

        auto seedFromUser = [&](int uid) {
            auto& posts = tweets[uid];
            if (!posts.empty()) {
                int lastIdx = posts.size() - 1;
                heap.push({posts[lastIdx].first, posts[lastIdx].second, uid, lastIdx});
            }
        };

        seedFromUser(userId);                          // include the user's own tweets
        for (int followeeId : following[userId]) seedFromUser(followeeId);

        vector<int> result;
        while (!heap.empty() && (int)result.size() < 10) {
            auto [ts, tweetId, uid, idx] = heap.top(); heap.pop();
            result.push_back(tweetId);

            if (idx > 0) {                              // push that user's next-most-recent tweet
                auto& posts = tweets[uid];
                heap.push({posts[idx - 1].first, posts[idx - 1].second, uid, idx - 1});
            }
        }
        return result;
    }

private:
    int timestamp = 0;
    unordered_map<int, vector<pair<int,int>>> tweets;     // userId -> [{timestamp, tweetId}]
    unordered_map<int, unordered_set<int>> following;
};

Seeding the heap with only one tweet per source (the most recent) rather than every tweet from every followed user is the key efficiency move — it keeps the heap size bounded by the number of people followed rather than by total tweet count. Popping a user's newest tweet and immediately pushing their next-most-recent one is exactly the lazy, on-demand expansion that makes a k-sorted-lists merge run in O(k log k) per feed entry instead of loading and sorting every tweet from every source up front.

"Merge k sorted lists" is a heap-shaped signal

Whenever a design problem's real bottleneck is combining several already-ordered streams into one ordered output — merge k sorted arrays, merge k linked lists, or this news feed — seed a heap with one element per stream and repeatedly pop-then-refill from whichever stream just contributed. It's the single most reusable move in this whole section.

5. Hands-on Exercise

Hands-on

Build and stress-test all four designs

Implement each structure and verify its complexity guarantees hold under load, not just on small examples.

Requirements:

  1. Implement LRUCache with capacity 2, and trace through a sequence of put/get calls by hand first; confirm your implementation's output matches your hand trace exactly.
  2. Implement MinStack and add a test that pushes a strictly decreasing sequence of values, confirming getMin updates correctly after each push and each pop.
  3. Implement MyHashMap and insert at least 1000 keys; add an assertion that the average bucket length after all insertions stays under 2, confirming the resize logic is actually keeping the load factor in check.
  4. Implement Twitter and test a scenario with at least 3 users, where one user follows both others, confirming getNewsFeed returns tweets from all three sources correctly interleaved by recency.
  5. For the LRU cache, add an LFUCache variant as a stretch goal: instead of evicting the least-recently-used entry, evict the least-frequently-used one, breaking ties by least-recently-used. State in a comment what additional structure this requires beyond the LRU design.
Hint

For requirement 5, LFU needs a frequency count per key and a way to quickly find "the least-frequently-used key, tie-broken by recency" — a common approach is a hash map from frequency to a doubly linked list of keys at that frequency (each an LRU list in its own right), plus tracking the current minimum frequency.

6. Knowledge Check

Four quick questions. Expand each to check your answer.

Q1

Why does the LRU cache need both a hash map and a doubly linked list — why wouldn't either structure alone be enough?

A hash map alone gives O(1) lookup by key but has no notion of "which entry was used least recently," so eviction would require an O(n) scan. A linked list alone can track recency order with O(1) reordering once you have the node, but finding the node for a given key would require an O(n) search. Combining them gives the map an O(1) way to jump directly to the right list node, and the list an O(1) way to reorder or evict once found.

Q2

In the min stack, why does popping from data also require popping from minStack, rather than leaving minStack untouched?

minStack.top() is only correct because it was computed as the minimum including the element that push just added to data. If that element is popped from data but its corresponding minimum value stays on minStack, getMin would keep reporting a minimum that includes an element no longer in the stack, which can be wrong once the true minimum was that now-removed element.

Q3

What is the actual worst-case time complexity of get in the from-scratch MyHashMap, and under what condition does that worst case happen?

The worst case is O(n), happening when every inserted key hashes into the same bucket — the load-factor resize keeps the average bucket length small in the typical case, but it can't prevent a pathological key distribution or a poorly chosen hash function from concentrating every key into one bucket's linked list, which then has to be scanned linearly.

Q4

In Design Twitter's getNewsFeed, why does the heap only ever hold at most one entry per followed user at a time, instead of every tweet from every followed user?

Because each user's own tweet list is already sorted by recency, the next tweet the feed could possibly need from a given user is always their current most-recent unconsumed one — every older tweet from that user is guaranteed to come later in the merged order. Seeding and refilling one entry per user at a time keeps the heap's size bounded by the number of followed users rather than by total tweet volume, which is what keeps the merge efficient.

← Back to Week 16: Advanced Strings Up next Week 18: Advanced Dynamic Programming →