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 Dictionary 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 Dictionaries 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 Dictionary 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.List<int> holds the values, so items[rng.Next(items.Count)] picks one in O(1).LinkedHashMap and Python has OrderedDict. .NET has no built-in LinkedHashMap. The short version is two BCL types glued together: a LinkedList<T> for the order, and a Dictionary<TKey, LinkedListNode<T>> that maps each key to its node. The node handle is the key idea. list.Remove(node) and list.AddLast(node) take the node itself, so both are O(1) with no search. AddLast(value) returns the new node, which is the handle you store. Problem 1 shows this version next to the hand-written one.
list.Remove(value). The overload that takes a value searches the list, so it is O(n).OrderedDictionary<TKey, TValue> arrived in .NET 9. It keeps insertion order, but it is backed by an array. Removing a key shifts the rest, so it is O(n). It does not fit an LRU cache.SortedDictionary orders by key, not by use. Wrong tool here./// <summary>One entry in a doubly linked list: a key, a value, and two links.</summary>
public sealed class DNode(int key = 0, int value = 0)
{
// Defaults of 0 exist only for the sentinels. Nobody reads their fields.
public int Key = key; // kept so eviction can delete the map entry
public int Value = value; // the payload
public DNode? Prev; // neighbour on the oldest side
public DNode? Next; // neighbour on the newest side
}
/// <summary>A Dictionary whose keys also sit in a doubly linked list, oldest first.</summary>
/// <example>
/// Add(1, 10), Add(2, 20), Add(1, 11), then PopOldest() returns 2.
/// </example>
public sealed class LinkedHashMap
{
private readonly Dictionary<int, DNode> map = []; // key to its node: the lookup half
private readonly DNode head = new(); // sentinel just before the oldest node
private readonly DNode tail = new(); // sentinel just after the newest node
/// <summary>Starts empty: the two sentinels point at each other.</summary>
public LinkedHashMap()
{
head.Next = tail; // empty list: the two sentinels touch
tail.Prev = head; // and they point at each other both ways
}
/// <summary>Number of keys stored.</summary>
public int Count => map.Count;
/// <summary>Cut node out in O(1). Sentinels guarantee both neighbours exist.</summary>
private static void Unlink(DNode node)
{
node.Prev!.Next = node.Next; // left neighbour now skips over node
node.Next!.Prev = node.Prev; // right neighbour now skips back over node
}
/// <summary>Put node at the newest end, just before the tail sentinel.</summary>
private void Append(DNode node)
{
var last = 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 = tail; // node points forward to the sentinel
tail.Prev = node; // sentinel points back to node
}
/// <summary>Insert or overwrite key, and make it the newest.</summary>
/// <param name="key">The key.</param>
/// <param name="value">The value to store.</param>
/// <example>Add(1, 10) stores 1 as the newest key.</example>
public void Add(int key, int value)
{
// Already present: take the old node out so the key is not listed twice.
if (map.TryGetValue(key, out var old))
Unlink(old);
var node = new DNode(key, value); // a fresh node for this key
map[key] = node; // map now points at the fresh node
Append(node); // and the list holds it at the newest end
}
/// <summary>Remove the oldest key from both structures and return it.</summary>
/// <returns>The oldest key.</returns>
/// <example>After Add(1, 10) and Add(2, 20), PopOldest() returns 1.</example>
public int PopOldest()
{
if (map.Count == 0) // 0 keys: head.Next is the tail sentinel
throw new InvalidOperationException("empty");
var node = head.Next!; // first real node: the oldest
Unlink(node); // gone from the list
map.Remove(node.Key); // gone from the map, using the stored key
return node.Key;
}
}
Two rules keep the structures in sync. Every method that touches the Dictionary also touches the list, in the same call. Every node knows its own key, so the list can find its way back to the Dictionary.
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.
/// <summary>A set with O(1) add, discard and random pick.</summary>
/// <example>Add(5), Add(7), Discard(5), then Items is [7] and Pick() returns 7.</example>
public sealed class SwapRemoveBag(Random? rng = null)
{
private readonly Random rng = rng ?? Random.Shared; // pass a seeded Random in tests
private readonly List<int> items = []; // the values, packed with no gaps
private readonly Dictionary<int, int> index = []; // value to its slot in items
/// <summary>The stored values, in slot order.</summary>
public IReadOnlyList<int> Items => items;
/// <summary>Append value if it is new.</summary>
/// <param name="value">The value to add.</param>
/// <example>Add(5) on an empty bag makes Items [5].</example>
public void Add(int value)
{
// Count before the append is exactly the slot the new value will land in.
// TryAdd returns false when value is already stored: a set holds one copy.
if (index.TryAdd(value, items.Count))
items.Add(value);
}
/// <summary>Remove value if present, without leaving a gap.</summary>
/// <param name="value">The value to remove.</param>
/// <example>Discard(5) on [5, 7] leaves [7].</example>
public void Discard(int value)
{
// Remove with out gives the slot and deletes the entry in one lookup.
if (!index.Remove(value, out int hole))
return; // nothing to remove
int lastSlot = items.Count - 1; // - 1: index of the final slot
int last = items[lastSlot];
items.RemoveAt(lastSlot); // removing the final slot is O(1)
if (hole < items.Count)
{
// The removed value was not the last one. Move last into the hole.
items[hole] = last; // fill the gap
index[last] = hole; // and tell the map where last went
}
}
/// <summary>Return a uniformly random stored value.</summary>
/// <returns>One stored value. Items has no gaps, so each is equally likely.</returns>
/// <example>Pick() on [7] returns 7.</example>
public int Pick() => items[rng.Next(items.Count)]; // Next(n): 0 .. n - 1
}
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 rng.Next(items.Count) 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 RemoveAt drops. The index line is the Dictionary. Notice it is fixed for 7 before key 5 is deleted.
prev and next.Dictionary order. Its enumeration order is not guaranteed. It often looks like insertion order until a key is removed, then new keys fill old slots. Never use it as the recency list.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./// <summary>A doubly linked list node that remembers its own key.</summary>
public sealed class LruNode(int key = 0, int value = 0)
{
// Defaults of 0 are for the two sentinels only. Their fields are never read.
public int Key = key; // needed to delete from the map on evict
public int Value = value; // the cached value
public LruNode? Prev; // toward head: less recently used
public LruNode? Next; // toward tail: more recently used
}
/// <summary>Least recently used cache with O(1) Get and Put.</summary>
/// <example>
/// new LruCache(2): Put(1, 1), Put(2, 2), Get(1) is 1, Put(3, 3), then Get(2) is -1.
/// </example>
public sealed class LruCache
{
private readonly int capacity;
private readonly Dictionary<int, LruNode> nodes = []; // key to node: O(1) lookup
private readonly LruNode head = new(); // sentinel, head.Next is least recent
private readonly LruNode tail = new(); // sentinel, tail.Prev is most recent
/// <summary>Creates an empty cache.</summary>
/// <param name="capacity">Maximum number of keys kept, 0 or more.</param>
public LruCache(int capacity)
{
this.capacity = capacity;
head.Next = tail; // empty cache: sentinels touch
tail.Prev = head; // in both directions
}
/// <summary>Unlink node. Sentinels mean Prev and Next are never null.</summary>
private static void Remove(LruNode node)
{
node.Prev!.Next = node.Next; // left neighbour skips node
node.Next!.Prev = node.Prev; // right neighbour skips node
}
/// <summary>Link node in just before tail: the most recent spot.</summary>
private void AddToEnd(LruNode node)
{
var last = 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 = tail; // node points to the sentinel
tail.Prev = node; // sentinel points back to node
}
/// <summary>Return the value for key and mark it most recent, or -1.</summary>
/// <param name="key">The key to look up.</param>
/// <returns>The cached value, or -1 when the key is missing.</returns>
/// <example>Get(1) after Put(1, 5) returns 5.</example>
public int Get(int key)
{
if (!nodes.TryGetValue(key, out var node))
return -1; // -1: the problem's "not found" value
// A read is a use: move the node to the most recent end.
Remove(node);
AddToEnd(node);
return node.Value;
}
/// <summary>Insert or update key, mark it most recent, evict if over capacity.</summary>
/// <param name="key">The key.</param>
/// <param name="value">The value to cache.</param>
/// <example>Put(1, 5) then Get(1) returns 5.</example>
public void Put(int key, int value)
{
if (nodes.TryGetValue(key, out var node))
{
node.Value = value; // overwrite in place, no new node
Remove(node); // and move it to the most recent end
AddToEnd(node);
return;
}
node = new LruNode(key, value); // brand new key
nodes[key] = node; // map half
AddToEnd(node); // list half
if (nodes.Count > capacity)
{
// One over capacity: drop the least recent, the node after head.
var oldest = head.Next!;
Remove(oldest); // out of the list
nodes.Remove(oldest.Key); // out of the map, via its stored key
}
}
}
This is the .NET answer to Python’s OrderedDict version. There is no built-in LinkedHashMap, so you glue LinkedList<T> to a Dictionary of its nodes. The BCL list has no sentinels to manage and no pointer code to get wrong.
/// <summary>Same cache, with the BCL LinkedList as the list half.</summary>
/// <example>
/// new LruCacheBcl(2): Put(1, 1), Put(2, 2), Get(1) is 1, Put(3, 3), then Get(2) is -1.
/// </example>
public sealed class LruCacheBcl(int capacity)
{
// First is least recent, Last is most recent. Each node carries its own key.
private readonly LinkedList<(int Key, int Value)> order = new();
// Key to its node handle. The handle is what makes Remove(node) O(1).
private readonly Dictionary<int, LinkedListNode<(int Key, int Value)>> nodes = [];
/// <summary>Return the value for key and mark it most recent, or -1.</summary>
/// <param name="key">The key to look up.</param>
/// <returns>The cached value, or -1 when the key is missing.</returns>
/// <example>Get(1) after Put(1, 5) returns 5.</example>
public int Get(int key)
{
if (!nodes.TryGetValue(key, out var node))
return -1; // -1: the problem's "not found" value
order.Remove(node); // O(1): unlink by handle, no search
order.AddLast(node); // O(1): relink the same node at the recent end
return node.Value.Value; // node.Value is the tuple, .Value its value
}
/// <summary>Insert or update key, mark it most recent, evict if over capacity.</summary>
/// <param name="key">The key.</param>
/// <param name="value">The value to cache.</param>
/// <example>Put(1, 5) then Get(1) returns 5.</example>
public void Put(int key, int value)
{
if (nodes.TryGetValue(key, out var node))
{
node.Value = (key, value); // overwrite in place, keep the same node
order.Remove(node); // an update is a use too
order.AddLast(node);
return;
}
nodes[key] = order.AddLast((key, value)); // AddLast returns the new handle
if (nodes.Count > capacity)
{
var oldest = order.First!; // least recent sits at the front
order.RemoveFirst();
nodes.Remove(oldest.Value.Key); // the stored key cleans the map
}
}
}
Three details matter. AddLast((key, value)) returns the node, so the map stores it in the same line. order.Remove(node) takes the node, not the value, so it never searches. The tuple keeps the key on the node, so eviction can clean the map. The node is reused on every move, so a hit allocates nothing.
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 use bool TryGet(int key, out int value), the usual .NET shape.Design a stack with Push, Pop, Top and GetMin, all in O(1). LeetCode calls the last one getMin. You may assume Pop, Top and GetMin are only called on a non-empty stack.
<= the current minimum. It saves space when minimums change rarely. Same big O./// <summary>A stack that also reports its minimum in O(1).
/// Each entry is a pair (value, minimum of this entry and all below it).</summary>
/// <example>
/// Push(-2), Push(0), Push(-3): GetMin() is -3. Pop(), then Top() is 0, GetMin() is -2.
/// </example>
public sealed class MinStack
{
// Invariant: each pair's Min is the min of its value and every value below it.
private readonly Stack<(int Value, int Min)> pairs = new();
/// <summary>Push value with a snapshot of the minimum so far.</summary>
/// <param name="value">The value to push.</param>
/// <example>Push(4) on an empty stack makes GetMin() return 4.</example>
public void Push(int value)
{
// An empty stack: the first entry is its own minimum.
// Otherwise compare with the top entry's stored minimum.
int low = pairs.Count == 0 ? value : Math.Min(value, pairs.Peek().Min);
pairs.Push((value, low));
}
/// <summary>Remove the top entry. Entries below keep their own correct minimums.</summary>
/// <example>Push(1), Push(2), Pop(), then Top() returns 1.</example>
public void Pop() => pairs.Pop(); // throws InvalidOperationException when empty
/// <summary>Return the newest value.</summary>
/// <returns>The top value.</returns>
/// <example>Push(3) then Top() returns 3.</example>
public int Top() => pairs.Peek().Value;
/// <summary>Return the minimum of the whole stack.</summary>
/// <returns>The smallest stored value.</returns>
/// <example>Push(3), Push(1) then GetMin() returns 1.</example>
public int GetMin() => pairs.Peek().Min;
}
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).GetMin(): top pair's minimum, -3.Pop(), then Top() is 0 and GetMin() 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 GetMin() 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.Stack<T>.Peek and Pop throw InvalidOperationException. 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 GetRandom(), each in average O(1). Insert and Remove return whether they changed the set. GetRandom returns each stored value with equal probability. LeetCode calls it getRandom.
HashSet<int> does insert and remove, but picking a random element needs an O(n) walk. ElementAt(i) on it is that walk.List<int> does random pick with Random.Next, but RemoveAt in the middle shifts every later item, so it is O(n)./// <summary>Set with O(1) insert, remove and uniform random pick.</summary>
/// <example>
/// Insert(1) is true, Remove(2) is false, Insert(2) is true, Remove(1) is true,
/// Insert(2) is false, then GetRandom() returns 2.
/// </example>
public sealed class RandomizedSet(Random? rng = null)
{
private readonly Random rng = rng ?? Random.Shared; // seed it in tests
// Invariant: values has no gaps, and values[index[v]] == v for every v.
private readonly List<int> values = [];
private readonly Dictionary<int, int> index = []; // value to its slot in values
/// <summary>Add val.</summary>
/// <param name="val">The value to add.</param>
/// <returns>False if it was already present.</returns>
/// <example>Insert(1) on an empty set returns true.</example>
public bool Insert(int val)
{
// Count before the append is the slot the new value takes.
if (!index.TryAdd(val, values.Count))
return false; // sets hold one copy
values.Add(val);
return true;
}
/// <summary>Delete val by moving the last value into its slot.</summary>
/// <param name="val">The value to delete.</param>
/// <returns>False if it was not present.</returns>
/// <example>Remove(1) after Insert(1) returns true.</example>
public bool Remove(int val)
{
if (!index.TryGetValue(val, out int hole))
return false; // nothing to delete
int lastSlot = values.Count - 1; // - 1: the final slot, cheap to remove
int last = values[lastSlot];
values[hole] = last; // last value fills the hole
index[last] = hole; // record the move in the map
values.RemoveAt(lastSlot); // drop the now duplicate final slot
// Delete after the update above. If val was last, this removes it for good.
index.Remove(val);
return true;
}
/// <summary>Return a random stored value.</summary>
/// <returns>A stored value. No gaps, so every value is equally likely.</returns>
/// <example>GetRandom() on a set holding only 2 returns 2.</example>
public int GetRandom() => values[rng.Next(values.Count)]; // Next(n): 0 .. n - 1
}
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 Dictionary. Red is the value being removed, amber is the moved value, and grey is the duplicate that RemoveAt drops. Green means both structures agree at the end.
GetRandom on an empty set: rng.Next(0) returns 0, then the list index throws ArgumentOutOfRangeException. Ask what is wanted.List<T>.Add. Say the word “amortised”.new Random(7) through the constructor, or test only on a one-element set, as the tests do.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 a LinkedList<int> of the keys with that count, oldest first. Each bucket is a little LRU list.handles maps each key to its LinkedListNode<int>, so a key leaves its bucket in O(1).minFreq remembers the smallest count that has keys. Eviction pops the oldest key from buckets[minFreq].f to bucket f + 1. If bucket f empties and it was minFreq, then minFreq becomes f + 1. Nothing else can be lower, because the key just left that bucket.minFreq to 1. So minFreq never needs a scan./// <summary>Least frequently used cache, LRU among ties, O(1) Get and Put.</summary>
/// <example>
/// new LfuCache(2): Put(1, 1), Put(2, 2), Get(1) is 1, Put(3, 3), then Get(2) is -1.
/// </example>
public sealed class LfuCache(int capacity)
{
private readonly Dictionary<int, int> values = []; // key to value
private readonly Dictionary<int, int> freq = []; // key to how many times it was used
// Count to the keys with that count, oldest first. Each bucket is a little LRU list.
private readonly Dictionary<int, LinkedList<int>> buckets = [];
// Key to its node inside its bucket, so leaving a bucket is O(1).
private readonly Dictionary<int, LinkedListNode<int>> handles = [];
private int minFreq; // starts 0: no keys yet. Set on first insert.
/// <summary>Append key at the recent end of bucket count, creating it if needed.</summary>
private void Join(int key, int count)
{
if (!buckets.TryGetValue(count, out var bucket))
buckets[count] = bucket = new LinkedList<int>();
handles[key] = bucket.AddLast(key); // AddLast: most recent within the bucket
}
/// <summary>Record one more use of key: move it up one frequency bucket.</summary>
private void Touch(int key)
{
int count = freq[key]; // current count, before this use
var bucket = buckets[count];
bucket.Remove(handles[key]); // leave the old bucket in O(1) by handle
if (bucket.Count == 0) // 0: the bucket just emptied
{
buckets.Remove(count); // drop empty buckets to keep memory tidy
if (minFreq == 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.
minFreq = count + 1;
}
}
freq[key] = count + 1; // + 1: this use
Join(key, count + 1); // + 1: the next bucket up
}
/// <summary>Return the value for key and count the use, or -1.</summary>
/// <param name="key">The key to look up.</param>
/// <returns>The cached value, or -1 when the key is missing.</returns>
/// <example>Get(1) after Put(1, 5) returns 5.</example>
public int Get(int key)
{
if (!values.TryGetValue(key, out int value))
return -1; // -1: the problem's "not found" value
Touch(key);
return value;
}
/// <summary>Insert or update key. Evict the LFU key first if the cache is full.</summary>
/// <param name="key">The key.</param>
/// <param name="value">The value to cache.</param>
/// <example>Put(1, 5) then Get(1) returns 5.</example>
public void Put(int key, int value)
{
if (capacity <= 0)
return; // 0 capacity: nothing can be stored
if (values.ContainsKey(key))
{
values[key] = value; // update counts as a use
Touch(key);
return;
}
if (values.Count == capacity)
{
var bucket = buckets[minFreq];
int victim = bucket.First!.Value; // the oldest key among the least frequent
bucket.RemoveFirst();
if (bucket.Count == 0) // 0: bucket emptied, so remove it
buckets.Remove(minFreq);
values.Remove(victim); // victim leaves every map
freq.Remove(victim);
handles.Remove(victim);
}
values[key] = value;
freq[key] = 1; // 1: a new key has been used once
Join(key, 1); // 1: join the count-one bucket at the end
minFreq = 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], minFreq 1.Get(1): key 1 moves up. 1: [2], 2: [1]. Bucket 1 is not empty, so minFreq 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 minFreq, so minFreq becomes 2. 2: [1, 3].Put(4): full. Evict the oldest in bucket 2, key 1. Add 4: 1: [4], 2: [3], minFreq 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 minFreq. 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.LinkedList in arrival order, so the front is the LRU key.LinkedList<T>: each bucket becomes a hand-written doubly linked list with sentinels, the LRU code from problem 1, one per count.Dictionary of LinkedListNode handles plus a LinkedList<T>. Offer it, then write the list by hand if asked.minFreq 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.