No single built-in structure does everything in O(1). So you glue two together. The hash map finds things. The second structure keeps order or picks at random.
Design questions read like a spec: “build a class with these methods, each in O(1)”. They feel open-ended, but nearly all of them have the same answer. Ask what the dict cannot do by itself. Then add one structure that does exactly that, and keep the two in sync on every call.
Reading the figure. Violet boxes are the dicts and violet arrows are the pointers they store. In pair one, each blue node links forward on the top arrow and back on the bottom arrow. The grey sentinels hold no data, so every real node always has two neighbours. In pair two, the dict maps a value to its slot, and the array has no gaps.
head and tail, sit at the ends and hold no data. Every real node then has two neighbours, so unlink and append never branch on “is the list empty”. This is the dummy-node trick applied to both ends.random.choice picks one in O(1).collections.OrderedDict is pair one, already built. It is a dict backed by a doubly linked list. move_to_end(key) marks a key as newest. popitem(last=False) removes the oldest. An LRU cache is about ten lines with it. Plain dict keeps insertion order too, but it has no O(1) move-to-end. Interviewers often forbid OrderedDict for LRU, because the question exists to test whether you can build the linked list and keep two structures in sync. Offer it first as the production answer. Then say you will write the list by hand, and do it.class DNode:
"""One entry in a doubly linked list: a key, a value, and two links."""
# __slots__: a fixed set of fields, so each node uses less memory.
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key: int = 0, value: int = 0) -> None:
# Defaults of 0 exist only for the sentinels. Nobody reads their fields.
self.key = key # kept so eviction can delete the dict entry
self.value = value # the payload
self.prev: "DNode | None" = None # neighbour on the oldest side
self.next: "DNode | None" = None # neighbour on the newest side
class LinkedHashMap:
"""A dict whose keys also sit in a doubly linked list, oldest first.
Example:
>>> table = LinkedHashMap()
>>> table.add(1, 10)
>>> table.add(2, 20)
>>> table.add(1, 11)
>>> table.pop_oldest()
2
"""
def __init__(self) -> None:
self.map: dict[int, DNode] = {} # key to its node: the O(1) lookup half
self.head = DNode() # sentinel just before the oldest node
self.tail = DNode() # sentinel just after the newest node
self.head.next = self.tail # empty list: the two sentinels touch
self.tail.prev = self.head # and they point at each other both ways
def _unlink(self, node: DNode) -> None:
"""Cut node out in O(1). Sentinels guarantee both neighbours exist."""
node.prev.next = node.next # left neighbour now skips over node
node.next.prev = node.prev # right neighbour now skips back over node
def _append(self, node: DNode) -> None:
"""Put node at the newest end, just before the tail sentinel."""
last = self.tail.prev # current newest node, or head if empty
last.next = node # old newest points forward to node
node.prev = last # node points back to old newest
node.next = self.tail # node points forward to the sentinel
self.tail.prev = node # sentinel points back to node
def add(self, key: int, value: int) -> None:
"""Insert or overwrite key, and make it the newest."""
if key in self.map:
# Already present: take the old node out so the key is not listed twice.
self._unlink(self.map[key])
node = DNode(key, value) # a fresh node for this key
self.map[key] = node # dict now points at the fresh node
self._append(node) # and the list holds it at the newest end
def pop_oldest(self) -> int:
"""Remove the oldest key from both structures and return it."""
node = self.head.next # first real node: the oldest
self._unlink(node) # gone from the list
del self.map[node.key] # gone from the dict, using the stored key
return node.key
Two rules keep the structures in sync. Every method that touches the dict also touches the list, in the same call. Every node knows its own key, so the list can find its way back to the dict.
Reading the figure. Top arrows are next and bottom arrows are prev. Amber arrows are the ones each method writes, numbered in code order. On the left, A and B skip over X, so X drops out. Its own links are left alone, which is harmless. On the right, N slides in between the old newest node and the tail sentinel.
import random
class SwapRemoveBag:
"""A set with O(1) add, discard and random pick.
Example:
>>> bag = SwapRemoveBag()
>>> bag.add(5)
>>> bag.add(7)
>>> bag.discard(5)
>>> bag.items
[7]
>>> bag.pick()
7
"""
def __init__(self) -> None:
self.items: list[int] = [] # the values, packed with no gaps
self.index: dict[int, int] = {} # value to its slot in items
def add(self, value: int) -> None:
"""Append value if it is new."""
if value in self.index:
return # already stored: a set holds one copy
# len before the append is exactly the slot the new value will land in.
self.index[value] = len(self.items)
self.items.append(value)
def discard(self, value: int) -> None:
"""Remove value if present, without leaving a gap."""
if value not in self.index:
return # nothing to remove
hole = self.index.pop(value) # slot the value leaves empty
last = self.items.pop() # pop the final slot: O(1) at the end
if hole < len(self.items):
# The removed value was not the last one. Move last into the hole.
self.items[hole] = last # fill the gap
self.index[last] = hole # and tell the dict where last went
def pick(self) -> int:
"""Return a uniformly random stored value. Items has no gaps, so it is fair."""
return random.choice(self.items)
Order inside a list rarely matters for a set, so you are free to break it. Swapping the last value into the hole costs O(1) and keeps the array dense, which is what makes random.choice fair.
Reading the figure. The red cell is the value being removed. The amber cell is the last value after it moves into the hole. The grey cell is the old copy, which pop drops. The index line is the dict. Notice it is fixed for 7 before key 5 is deleted.
prev and next.dict as the ordered structure. It keeps insertion order, but re-inserting a key does not move it. You need pop then re-insert, or OrderedDict.Design a cache with a fixed capacity. get(key) returns the value, or -1 if the key is missing. put(key, value) inserts or updates. When the cache grows past capacity, evict the least recently used key. Both methods must run in O(1). Both a get and a put count as a use.
head, to most recent, next to tail.get: look up the node, move it to the tail end, return its value.put: if the key exists, update the value and move it. If not, append a new node. Then, if the size passed capacity, evict head.next.capacity = 0 with no extra branch.class LRUNode:
"""A doubly linked list node that remembers its own key."""
# __slots__: fixed fields, less memory per cached entry.
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key: int = 0, value: int = 0) -> None:
# Defaults of 0 are for the two sentinels only. Their fields are never read.
self.key = key # needed to delete from the dict on evict
self.value = value # the cached value
self.prev: "LRUNode | None" = None # toward head: less recently used
self.next: "LRUNode | None" = None # toward tail: more recently used
class LRUCache:
"""Least recently used cache with O(1) get and put.
Args:
capacity: Maximum number of keys kept, capacity >= 0.
Returns:
get returns the value, or -1 when the key is missing.
Example:
>>> cache = LRUCache(2)
>>> cache.put(1, 1)
>>> cache.put(2, 2)
>>> cache.get(1)
1
>>> cache.put(3, 3)
>>> cache.get(2)
-1
>>> cache.put(4, 4)
>>> cache.get(1)
-1
>>> cache.get(3)
3
>>> cache.get(4)
4
"""
def __init__(self, capacity: int) -> None:
self.capacity = capacity
self.nodes: dict[int, LRUNode] = {} # key to node: O(1) lookup
self.head = LRUNode() # sentinel, head.next is least recent
self.tail = LRUNode() # sentinel, tail.prev is most recent
self.head.next = self.tail # empty cache: sentinels touch
self.tail.prev = self.head # in both directions
def _remove(self, node: LRUNode) -> None:
"""Unlink node. Sentinels mean prev and next are never None."""
node.prev.next = node.next # left neighbour skips node
node.next.prev = node.prev # right neighbour skips node
def _add_to_end(self, node: LRUNode) -> None:
"""Link node in just before tail: the most recent spot."""
last = self.tail.prev # current most recent, or head if empty
last.next = node # old most recent points to node
node.prev = last # node points back to it
node.next = self.tail # node points to the sentinel
self.tail.prev = node # sentinel points back to node
def get(self, key: int) -> int:
"""Return the value for key and mark it most recent, or -1."""
node = self.nodes.get(key) # None when key is absent
if node is None:
return -1 # -1: the problem's "not found" value
# A read is a use: move the node to the most recent end.
self._remove(node)
self._add_to_end(node)
return node.value
def put(self, key: int, value: int) -> None:
"""Insert or update key, mark it most recent, evict if over capacity."""
node = self.nodes.get(key) # existing node, or None
if node is not None:
node.value = value # overwrite in place, no new node
self._remove(node) # and move it to the most recent end
self._add_to_end(node)
return
node = LRUNode(key, value) # brand new key
self.nodes[key] = node # dict half
self._add_to_end(node) # list half
if len(self.nodes) > self.capacity:
# One over capacity: drop the least recent, the node after head.
oldest = self.head.next
self._remove(oldest) # out of the list
del self.nodes[oldest.key] # out of the dict, via its stored key
from collections import OrderedDict
class LRUCacheOrdered:
"""Same cache, using OrderedDict as the dict plus linked list.
Args:
capacity: Maximum number of keys kept, capacity >= 0.
Returns:
get returns the value, or -1 when the key is missing.
Example:
>>> cache = LRUCacheOrdered(2)
>>> cache.put(1, 1)
>>> cache.put(2, 2)
>>> cache.get(1)
1
>>> cache.put(3, 3)
>>> cache.get(2)
-1
"""
def __init__(self, capacity: int) -> None:
self.capacity = capacity
# Front of the OrderedDict is least recent, the end is most recent.
self.data: OrderedDict[int, int] = OrderedDict()
def get(self, key: int) -> int:
"""Return the value for key and mark it most recent, or -1."""
if key not in self.data:
return -1 # -1: the problem's "not found" value
self.data.move_to_end(key) # O(1): relink to the most recent end
return self.data[key]
def put(self, key: int, value: int) -> None:
"""Insert or update key, mark it most recent, evict if over capacity."""
if key in self.data:
self.data.move_to_end(key) # an update is a use too
self.data[key] = value # new keys land at the end already
if len(self.data) > self.capacity:
# last=False pops from the front: the least recently used key.
self.data.popitem(last=False)
Capacity 2. The list is shown least recent first.
put(1, 1): list [1].put(2, 2): list [1, 2].get(1): returns 1, moves 1 to the end. List [2, 1].put(3, 3): list [2, 1, 3] is size 3, so evict the front, key 2. List [1, 3].get(2): missing, returns -1.put(4, 4): list [1, 3, 4], evict key 1. List [3, 4].Reading the figure. H and T are the sentinels. The amber key is the one the call just used, now at the most recent end. A red key was evicted from the head end because the size passed capacity 2. Notice that get(2) on a missing key leaves the order alone.
capacity = 0: every put inserts, then evicts itself at once. Every get returns -1.put on an existing key: updates the value and counts as a use. It must not grow the size.get on a missing key must not change the order.-1: the sentinel return becomes ambiguous. Ask, or return None instead.Design a stack with push, pop, top and get_min, all in O(1). LeetCode calls the last one getMin. You may assume pop, top and get_min are only called on a non-empty stack.
<= the current minimum. It saves space when minimums change rarely. Same big O.class MinStack:
"""A stack that also reports its minimum in O(1).
Each entry is a pair (value, minimum of this entry and all below it).
Args:
None. Start empty and call push.
Returns:
top returns the newest value. get_min returns the smallest stored value.
Example:
>>> stack = MinStack()
>>> stack.push(-2)
>>> stack.push(0)
>>> stack.push(-3)
>>> stack.get_min()
-3
>>> stack.pop()
>>> stack.top()
0
>>> stack.get_min()
-2
"""
def __init__(self) -> None:
# Invariant: pairs[i][1] is the min of pairs[0..i] values.
self.pairs: list[tuple[int, int]] = []
def push(self, value: int) -> None:
"""Push value with a snapshot of the minimum so far."""
if not self.pairs:
low = value # first entry is its own minimum
else:
# [-1] is the top entry. [1] is its stored minimum.
low = min(value, self.pairs[-1][1])
self.pairs.append((value, low))
def pop(self) -> None:
"""Remove the top entry. Entries below keep their own correct minimums."""
self.pairs.pop()
def top(self) -> int:
"""Return the newest value."""
return self.pairs[-1][0] # [-1]: top entry. [0]: its value
def get_min(self) -> int:
"""Return the minimum of the whole stack."""
return self.pairs[-1][1] # [-1]: top entry. [1]: min so far
push(-2): pairs [(-2, -2)].push(0): min of 0 and -2 is -2. Pairs [(-2, -2), (0, -2)].push(-3): min of -3 and -2 is -3. Pairs gain (-3, -3).get_min(): top pair's minimum, -3.pop(), then top() is 0 and get_min() is -2. The old minimum came back for free.Reading the figure. The stack grows upward. The amber pair is the top. The dashed red pair was just popped. The green line under each frame is what get_min() returns at that moment. Notice that the -2 comes back after the pop with no work at all.
1, 1 then popping once: the pair form handles it. The two-stack variant needs <=, not <, or it breaks here.IndexError from the list. Ask whether to raise a clearer error or return a sentinel.min for max. Popping the max from the middle is a harder question that needs a heap or sorted list.Design a set with insert(val), remove(val) and get_random(), each in average O(1). insert and remove return whether they changed the set. get_random returns each stored value with equal probability. LeetCode calls it getRandom.
set does insert and remove, but picking a random element needs an O(n) walk.random.choice, but removing from the middle is O(n).import random
class RandomizedSet:
"""Set with O(1) insert, remove and uniform random pick.
Args:
None. Start empty and call insert.
Returns:
insert and remove return True when the set changed.
get_random returns a stored value, each with equal chance.
Example:
>>> rs = RandomizedSet()
>>> rs.insert(1)
True
>>> rs.remove(2)
False
>>> rs.insert(2)
True
>>> rs.get_random() in {1, 2}
True
>>> rs.remove(1)
True
>>> rs.insert(2)
False
>>> rs.get_random()
2
"""
def __init__(self) -> None:
# Invariant: values has no gaps, and values[index[v]] == v for every v.
self.values: list[int] = []
self.index: dict[int, int] = {} # value to its slot in values
def insert(self, val: int) -> bool:
"""Add val. Return False if it was already present."""
if val in self.index:
return False # sets hold one copy
# len before the append is the slot the new value takes.
self.index[val] = len(self.values)
self.values.append(val)
return True
def remove(self, val: int) -> bool:
"""Delete val by moving the last value into its slot."""
if val not in self.index:
return False # nothing to delete
hole = self.index[val] # slot val occupies now
last = self.values[-1] # [-1]: the final slot, cheap to pop
self.values[hole] = last # last value fills the hole
self.index[last] = hole # record the move in the dict
self.values.pop() # drop the now duplicate final slot
# Delete after the update above. If val was last, this removes it for good.
del self.index[val]
return True
def get_random(self) -> int:
"""Return a random stored value. No gaps, so every value is equally likely."""
return random.choice(self.values)
Start with values [10, 20, 30] and index {10: 0, 20: 1, 30: 2}. Call remove(10).
hole = 0, last = 30.[30, 20, 30], index gets 30: 0.[30, 20].{30: 0, 20: 1}. Both structures agree again.Reading the figure. The top row is values with slot numbers under it. The index line is the dict. Red is the value being removed, amber is the moved value, and grey is the duplicate that pop drops. Green means both structures agree at the end.
get_random on an empty set: random.choice raises IndexError. Ask what is wanted.list.append. Say the word “amortised”.Design a cache with a fixed capacity, where get and put run in O(1). When full, evict the least frequently used key. If several keys tie on frequency, evict the least recently used of them. Both get and put on an existing key count as a use. A new key starts with frequency 1.
values maps key to value. freq maps key to its use count.buckets maps a count to an OrderedDict of the keys with that count, oldest first. Each bucket is a little LRU list.min_freq remembers the smallest count that has keys. Eviction pops the oldest key from buckets[min_freq].f to bucket f + 1. If bucket f empties and it was min_freq, then min_freq becomes f + 1. Nothing else can be lower, because the key just left that bucket.min_freq to 1. So min_freq never needs a scan.from collections import OrderedDict, defaultdict
class LFUCache:
"""Least frequently used cache, LRU among ties, O(1) get and put.
Args:
capacity: Maximum number of keys kept, capacity >= 0.
Returns:
get returns the value, or -1 when the key is missing.
Example:
>>> lfu = LFUCache(2)
>>> lfu.put(1, 1)
>>> lfu.put(2, 2)
>>> lfu.get(1)
1
>>> lfu.put(3, 3)
>>> lfu.get(2)
-1
>>> lfu.get(3)
3
>>> lfu.put(4, 4)
>>> lfu.get(1)
-1
>>> lfu.get(3)
3
>>> lfu.get(4)
4
"""
def __init__(self, capacity: int) -> None:
self.capacity = capacity
self.values: dict[int, int] = {} # key to value
self.freq: dict[int, int] = {} # key to how many times it was used
# count to the keys with that count, oldest first. Values are unused.
self.buckets: defaultdict[int, OrderedDict[int, None]] = defaultdict(
OrderedDict
)
self.min_freq = 0 # 0: no keys yet. Set on first insert.
def _touch(self, key: int) -> None:
"""Record one more use of key: move it up one frequency bucket."""
count = self.freq[key] # current count, before this use
bucket = self.buckets[count]
del bucket[key] # leave the old bucket
if not bucket:
del self.buckets[count] # drop empty buckets to keep memory tidy
if self.min_freq == count:
# The lowest bucket just emptied. This key now sits at count + 1,
# and no key has a smaller count, so + 1 is the new minimum.
self.min_freq = count + 1
self.freq[key] = count + 1 # + 1: this use
# None: the OrderedDict is used as an ordered set. Append = most recent.
self.buckets[count + 1][key] = None
def get(self, key: int) -> int:
"""Return the value for key and count the use, or -1."""
if key not in self.values:
return -1 # -1: the problem's "not found" value
self._touch(key)
return self.values[key]
def put(self, key: int, value: int) -> None:
"""Insert or update key. Evict the LFU key first if the cache is full."""
if self.capacity <= 0:
return # 0 capacity: nothing can be stored
if key in self.values:
self.values[key] = value # update counts as a use
self._touch(key)
return
if len(self.values) == self.capacity:
bucket = self.buckets[self.min_freq]
# last=False: pop the oldest key among the least frequent ones.
victim, _ = bucket.popitem(last=False)
if not bucket:
del self.buckets[self.min_freq] # bucket emptied: remove it
del self.values[victim] # victim leaves every map
del self.freq[victim]
self.values[key] = value
self.freq[key] = 1 # 1: a new key has been used once
self.buckets[1][key] = None # 1: join the count-one bucket at the end
self.min_freq = 1 # 1: nothing can have a lower count
Capacity 2. Buckets are shown as count: [keys, oldest first].
put(1), put(2): 1: [1, 2], min_freq 1.get(1): key 1 moves up. 1: [2], 2: [1]. Bucket 1 is not empty, so min_freq stays 1.put(3): full. Evict the oldest in bucket 1, key 2. Add 3: 1: [3], 2: [1].get(3): key 3 moves up. Bucket 1 empties and was min_freq, so min_freq becomes 2. 2: [1, 3].put(4): full. Evict the oldest in bucket 2, key 1. Add 4: 1: [4], 2: [3], min_freq 1.Reading the figure. Each row is the state after the call. The amber key is the one just used or added. A red key was evicted to make room. The green number is min_freq. Notice the jump to 2 after get(3) empties bucket 1, and the reset to 1 when key 4 arrives.
capacity = 0: put must return early. Otherwise the eviction branch reads an empty bucket and fails.OrderedDict is the built-in shortcut. Offer it, then write the list by hand, because that is what is being tested.min_freq that only moves when its bucket empties.That is the last pattern. Go back to the index and pick the pattern you are least sure of. Then work its problems again from a blank file, and say the approach out loud before you type. If linked lists felt shaky here, start with In-Place Reversal of a Linked List. The guides cover the mechanics around the patterns: the toolkit, constraints, the interview script and testing.