Design problems are a distinct interview category. They rarely need a clever algorithm; they need you to compose two ordinary data structures so that every required operation is $O(1)$.

The recurring move is always the same:

A hash map gives $O(1)$ lookup but no order. A linked list gives $O(1)$ insert and remove at a known position but no lookup. Put them together — the map storing pointers into the list — and you get both.

That single combination is the answer to LRU, LFU, and a surprising number of “design X with $O(1)$ everything” questions.

What you’ll learn

• Why a hash map alone, or a list alone, cannot meet the requirements.
• The map-to-node pattern, and Python’s OrderedDictOrderedDict shortcut.
• LFU: frequency buckets, and the min_freqmin_freq trick that keeps eviction $O(1)$.
• How to talk about design problems — clarify, state the invariant, then code.
• Three real LeetCode problems solved in the browser: 706, 146, 460.

The cue

Why one structure is not enough

The doubly linked list is essential rather than incidental: to unlink a node in $O(1)$ you need its predecessor, and only a prevprev pointer gives you that without searching.

The LRU template

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 = {}                      # key -> Node
        # sentinel head/tail remove every empty-list special case
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head
 
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def _add_front(self, node):            # front == most recently used
        node.next = self.head.next
        node.prev = self.head
        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)                 # a read counts as a use
        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           # back == least recently used
            self._remove(lru)
            del self.map[lru.key]          # the node stores its key FOR THIS

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 = {}                      # key -> Node
        # sentinel head/tail remove every empty-list special case
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head
 
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def _add_front(self, node):            # front == most recently used
        node.next = self.head.next
        node.prev = self.head
        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)                 # a read counts as a use
        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           # back == least recently used
            self._remove(lru)
            del self.map[lru.key]          # the node stores its key FOR THIS

The OrderedDictOrderedDict shortcut

Python’s collections.OrderedDictcollections.OrderedDict is a hash map plus a doubly linked list, with the two operations you need exposed directly:

from collections import OrderedDict
 
 
class LRUCache:
    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)          # O(1): mark most-recently used
        return self.data[key]
 
    def put(self, key, value):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.cap:
            self.data.popitem(last=False)   # O(1): evict the oldest

from collections import OrderedDict
 
 
class LRUCache:
    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)          # O(1): mark most-recently used
        return self.data[key]
 
    def put(self, key, value):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.cap:
            self.data.popitem(last=False)   # O(1): evict the oldest

LFU — frequency buckets

LFU evicts the least frequently used item, breaking ties by least recently used. The naive approach scans for the minimum frequency: $O(n)$ per eviction.

The $O(1)$ design keeps three structures:

• key_to_valkey_to_val — the values.
• key_to_freqkey_to_freq — each key’s use count.
• freq_to_keysfreq_to_keys — for each frequency, an OrderedDictOrderedDict of keys in LRU order. That inner ordering is what breaks ties.

Plus one integer: min_freqmin_freq.

The variant map

Practice — real LeetCode problems

LC 706 — Design HashMap · Easy

Problem. Design a MyHashMapMyHashMap without using any built-in hash table library. Support put(key, value)put(key, value), get(key)get(key) (returning -1-1 if absent), and remove(key)remove(key).

Constraints. 0 <= key, value <= 10^60 <= key, value <= 10^6, up to 10^410^4 calls.

Examples. put(1,1)put(1,1), put(2,2)put(2,2), get(1)get(1) gives 11, get(3)get(3) gives -1-1, put(2,1)put(2,1), get(2)get(2) gives 11, remove(2)remove(2), get(2)get(2) gives -1-1

LC 146 — LRU Cache · Medium

Problem. Design a cache with a fixed positive capacitycapacity supporting get(key)get(key) (returning -1-1 if absent) and put(key, value)put(key, value), evicting the least recently used key when capacity is exceeded. Both operations must run in $O(1)$ average time.

Constraints. 1 <= capacity <= 30001 <= capacity <= 3000, 0 <= key <= 10^40 <= key <= 10^4, 0 <= value <= 10^50 <= value <= 10^5, up to 2 * 10^52 * 10^5 calls.

Examples. With capacity 2: put(1,1)put(1,1), put(2,2)put(2,2), get(1)get(1) gives 11, put(3,3)put(3,3) evicts key 2, get(2)get(2) gives -1-1, put(4,4)put(4,4) evicts key 1, get(1)get(1) gives -1-1, get(3)get(3) gives 33, get(4)get(4) gives 44

LC 460 — LFU Cache · Hard

Problem. Design a cache with capacitycapacity supporting getget and putput in $O(1)$ average time, evicting the least frequently used key. When several keys tie on frequency, evict the least recently used among them. A getget or a putput of an existing key both count as a use.

Constraints. 0 <= capacity <= 10^40 <= capacity <= 10^4, 0 <= key, value <= 10^50 <= key, value <= 10^5, up to 2 * 10^52 * 10^5 calls.

Examples. With capacity 2: put(1,1)put(1,1), put(2,2)put(2,2), get(1)get(1) gives 11, put(3,3)put(3,3) evicts key 2 (frequency 1 versus key 1’s 2), get(2)get(2) gives -1-1, get(3)get(3) gives 33, put(4,4)put(4,4) evicts key 1, get(1)get(1) gives -1-1, get(3)get(3) gives 33, get(4)get(4) gives 44

LeetCode problem set

Interview follow-ups

Edge-case checklist

• Capacity 0 — legal in LC 460; putput must be a no-op. The most-failed detail.
• Capacity 1 — every insert evicts; exercises the eviction path immediately.
• putput on an existing key — must update the value and count as a use, not insert a duplicate.
• getget on a missing key — return -1-1, and do not create an entry or disturb frequencies.
• Eviction ties in LFU — equal frequencies break by least-recently-used; requires ordered buckets.
• putput overwriting in a hash bucket (LC 706) — replace, never append.
• Hash collisions (LC 706) — 11 and 10000011000001 share a bucket; the in-bucket key check matters.
• Evicting then inserting — set min_freq = 1min_freq = 1 after the eviction.

Recap

• Design problems are about composing structures, not clever algorithms. A hash map gives lookup; a doubly linked list gives order and $O(1)$ unlinking. Together they give $O(1)$ everything.
• Sentinel head/tail nodes remove every empty-list special case; store the key in each node so eviction can clean the map.
• Python’s OrderedDictOrderedDict is exactly this composition — move_to_endmove_to_end and popitem(last=False)popitem(last=False) are both $O(1)$. Know it, and be ready to build it by hand.
• LFU adds frequency buckets of OrderedDictOrderedDicts (so ties break by recency) plus a min_freqmin_freq integer that never needs searching.
• Guard capacity == 0capacity == 0 and remember a read counts as a use.
• Talk through the interface, the structures, and the invariant before coding — that is most of the score on a design question.

Next: Design with Stacks and Queues — building one primitive out of another, and the amortised argument that makes it efficient.