LRU Cache and Design Data Structure Interview Questions
Last updated 2026-11-19
Design questions ask you to build a small data structure with strict time bounds, usually O(1) per operation. The standard example is the LRU cache. They test whether you can combine basic structures, such as a hash map with a linked list or a list with an index map, to meet requirements that neither meets alone.
This page works through twelve designs, from min stack to the all-O(1) structure, with Python and Java code, complexity and edge cases. For the building blocks see arrays interview questions and heap interview questions. If the round also covers class design, see how to crack a low-level design interview.
| Goal | Meet O(1) or O(log n) per operation |
|---|---|
| Common combos | Hash map + linked list, list + index map |
| Cache policies | LRU, LFU |
| Also covered | Stacks, queues, rate limiting, snapshots |
The pattern and when to spot it
The prompt usually lists operations and their required complexity. Work out which operation each simple structure handles badly. A hash map gives O(1) lookup but no order. A linked list gives O(1) reorder and removal given a node but no lookup. Pair them, with the map storing node references, and both needs are met: that is the LRU cache. For random access plus fast delete, pair a list with a map of indexes and delete by swapping with the last element.
When data arrives over time, such as in the time-based store or the snapshot array, store versions per key in append order and use binary search to read them. Rate limiters and hit counters keep only the recent window, and lazily clean old data when queried. Always state what happens on edge inputs, such as an empty structure or a duplicate key, before coding.
Common mistakes
- Evicting from the linked list but forgetting to delete the key from the map. Store the key inside the node.
- Forgetting to refresh recency when put updates an existing key.
- Leaving empty buckets in frequency structures, which breaks min and max lookups.
- Using a deque or list scan for a window and claiming O(1) when the cleanup is amortised.
- Ignoring thread safety when the question mentions concurrent callers.
LRU Cache and Design Data Structure Interview Questions: questions with worked answers
1 Min stack: push, pop, top and getMin in O(1)
easyStore with each element the minimum of the stack at that moment, either as a pair on one stack or on a parallel stack. getMin reads the top pair. Popping restores the earlier minimum automatically, which is the point: no scan is ever needed. Time O(1) per operation, space O(n). Edge cases: getMin or pop on an empty stack (decide to throw or return a sentinel), duplicate minimum values, negative numbers.
pythonclass MinStack: def __init__(self): self.st = [] # (value, min so far) def push(self, x): m = min(x, self.st[-1][1]) if self.st else x self.st.append((x, m)) def pop(self): self.st.pop() def top(self): return self.st[-1][0] def get_min(self): return self.st[-1][1]javaclass MinStack { private final Deque<int[]> st = new ArrayDeque<>(); // {value, min so far} void push(int x) { int m = st.isEmpty() ? x : Math.min(x, st.peek()[1]); st.push(new int[]{x, m}); } void pop() { st.pop(); } int top() { return st.peek()[0]; } int getMin() { return st.peek()[1]; } }2 Queue using two stacks
easyPush onto an input stack. For pop or peek, if the output stack is empty, move every element from the input stack to it, which reverses the order so the oldest element is on top. Each element moves at most once, so operations are amortised O(1). Time amortised O(1) per operation, space O(n). Edge cases: pop on an empty queue, interleaved pushes and pops (only refill the output stack when it is empty), peek without popping.
pythonclass MyQueue: def __init__(self): self.inp, self.out = [], [] def push(self, x): self.inp.append(x) def _move(self): if not self.out: while self.inp: self.out.append(self.inp.pop()) def pop(self): self._move() return self.out.pop() def peek(self): self._move() return self.out[-1] def empty(self): return not self.inp and not self.outjavaclass MyQueue { private final Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>(); void push(int x) { in.push(x); } private void move() { if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop()); } int pop() { move(); return out.pop(); } int peek() { move(); return out.peek(); } boolean empty() { return in.isEmpty() && out.isEmpty(); } }3 LRU cache using the built-in ordered map
mediumLeast recently used eviction needs recency order plus O(1) lookup. Python OrderedDict and Java LinkedHashMap keep insertion order and can move a key to the end. On get, move the key to the most recent end. On put, insert or update and move to the end, then evict from the oldest end if over capacity. Time O(1) per operation, space O(capacity). Edge cases: capacity 1, updating an existing key (must refresh recency and not evict), get on a missing key (-1), eviction only after inserting beyond capacity.
pythonfrom collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cap = capacity self.d = OrderedDict() def get(self, key): if key not in self.d: return -1 self.d.move_to_end(key) return self.d[key] def put(self, key, value): self.d[key] = value self.d.move_to_end(key) if len(self.d) > self.cap: self.d.popitem(last=False)javaclass LRUCache extends LinkedHashMap<Integer, Integer> { private final int cap; LRUCache(int capacity) { super(16, 0.75f, true); // true = access order this.cap = capacity; } int get(int key) { return super.getOrDefault(key, -1); } void put(int key, int value) { super.put(key, value); } @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> e) { return size() > cap; } }4 LRU cache from scratch with a hash map and doubly linked list
mediumInterviewers often ask you to build the ordered map yourself. Keep a doubly linked list with the most recent node next to the head sentinel, and a hash map from key to node. get moves the node to the front. put updates or inserts at the front, and removes the node before the tail sentinel when capacity is exceeded, deleting its key from the map too. Sentinels remove null checks. Time O(1) per operation, space O(capacity). Edge cases: capacity of 1, evicting must also delete the map entry (the node stores its key), updating an existing key, a missing key returns -1.
pythonclass Node: def __init__(self, k=0, v=0): self.k, self.v, self.prev, self.next = k, v, None, None class LRUCache: def __init__(self, capacity): self.cap, self.map = capacity, {} self.head, self.tail = Node(), Node() self.head.next, self.tail.prev = self.tail, self.head def _remove(self, n): n.prev.next, n.next.prev = n.next, n.prev def _add_front(self, n): n.next, n.prev = self.head.next, self.head self.head.next.prev = n self.head.next = n def get(self, key): if key not in self.map: return -1 n = self.map[key] self._remove(n); self._add_front(n) return n.v def put(self, key, value): if key in self.map: n = self.map[key] n.v = value self._remove(n); self._add_front(n) return if len(self.map) == self.cap: lru = self.tail.prev self._remove(lru) del self.map[lru.k] n = Node(key, value) self.map[key] = n self._add_front(n)javaclass LRUCache { private static class Node { int k, v; Node prev, next; Node(int k, int v) { this.k = k; this.v = v; } } private final Map<Integer, Node> map = new HashMap<>(); private final Node head = new Node(0, 0), tail = new Node(0, 0); private final int cap; LRUCache(int capacity) { cap = capacity; head.next = tail; tail.prev = head; } private void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; } private void addFront(Node n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; } int get(int key) { Node n = map.get(key); if (n == null) return -1; remove(n); addFront(n); return n.v; } void put(int key, int value) { Node n = map.get(key); if (n != null) { n.v = value; remove(n); addFront(n); return; } if (map.size() == cap) { Node lru = tail.prev; remove(lru); map.remove(lru.k); } n = new Node(key, value); map.put(key, n); addFront(n); } }5 LFU cache: evict the least frequently used key
hardTrack each key value and use count, plus a map from count to the keys with that count in recency order, plus the current minimum count. get and put bump the key count: remove it from its count bucket, add it to the next one, and if the old bucket was the minimum and is now empty, raise the minimum. On inserting a new key at capacity, evict the oldest key in the minimum bucket, then reset the minimum to 1. Time O(1) per operation, space O(capacity). Edge cases: capacity 0 (ignore puts), ties on count broken by least recent, updating an existing key counts as a use, minimum frequency resets to 1 on every new key.
pythonfrom collections import defaultdict, OrderedDict class LFUCache: def __init__(self, capacity): self.cap = capacity self.val, self.freq = {}, {} self.buckets = defaultdict(OrderedDict) self.min_f = 0 def _touch(self, key): f = self.freq[key] del self.buckets[f][key] if not self.buckets[f] and self.min_f == f: self.min_f += 1 self.freq[key] = f + 1 self.buckets[f + 1][key] = None def get(self, key): if key not in self.val: return -1 self._touch(key) return self.val[key] def put(self, key, value): if self.cap == 0: return if key in self.val: self.val[key] = value self._touch(key) return if len(self.val) == self.cap: old, _ = self.buckets[self.min_f].popitem(last=False) del self.val[old], self.freq[old] self.val[key], self.freq[key] = value, 1 self.buckets[1][key] = None self.min_f = 1javaclass LFUCache { private final int cap; private int minF = 0; private final Map<Integer, Integer> val = new HashMap<>(), freq = new HashMap<>(); private final Map<Integer, LinkedHashSet<Integer>> buckets = new HashMap<>(); LFUCache(int capacity) { cap = capacity; } private void touch(int key) { int f = freq.get(key); LinkedHashSet<Integer> set = buckets.get(f); set.remove(key); if (set.isEmpty() && minF == f) minF++; freq.put(key, f + 1); buckets.computeIfAbsent(f + 1, x -> new LinkedHashSet<>()).add(key); } int get(int key) { if (!val.containsKey(key)) return -1; touch(key); return val.get(key); } void put(int key, int value) { if (cap == 0) return; if (val.containsKey(key)) { val.put(key, value); touch(key); return; } if (val.size() == cap) { LinkedHashSet<Integer> set = buckets.get(minF); int old = set.iterator().next(); set.remove(old); val.remove(old); freq.remove(old); } val.put(key, value); freq.put(key, 1); buckets.computeIfAbsent(1, x -> new LinkedHashSet<>()).add(key); minF = 1; } }6 Insert, delete and get random element in O(1)
mediumKeep the values in a list and a map from value to its index in the list. Insert appends and records the index. For delete, swap the target with the last element in the list, update the moved element index in the map, pop the list and remove the target from the map. getRandom picks a random index. Time O(1) average per operation, space O(n). Edge cases: inserting a duplicate (return false), deleting a missing value (false), deleting the last element (the swap is a no-op), updating the map in the right order when the removed element is last.
pythonimport random class RandomizedSet: def __init__(self): self.a, self.idx = [], {} def insert(self, v): if v in self.idx: return False self.idx[v] = len(self.a) self.a.append(v) return True def remove(self, v): if v not in self.idx: return False i, last = self.idx[v], self.a[-1] self.a[i] = last self.idx[last] = i self.a.pop() del self.idx[v] return True def get_random(self): return random.choice(self.a)javaclass RandomizedSet { private final List<Integer> a = new ArrayList<>(); private final Map<Integer, Integer> idx = new HashMap<>(); private final Random rnd = new Random(); boolean insert(int v) { if (idx.containsKey(v)) return false; idx.put(v, a.size()); a.add(v); return true; } boolean remove(int v) { Integer i = idx.get(v); if (i == null) return false; int last = a.get(a.size() - 1); a.set(i, last); idx.put(last, i); a.remove(a.size() - 1); idx.remove(v); return true; } int getRandom() { return a.get(rnd.nextInt(a.size())); } }7 Time-based key-value store
mediumset(key, value, timestamp) stores versions, and get(key, timestamp) returns the value with the largest timestamp not above the query. Timestamps for a key arrive in increasing order, so keep a list of timestamps and a parallel list of values per key and binary search for the rightmost timestamp at or before the query. Time O(1) set, O(log n) get, space O(n). Edge cases: no earlier timestamp (empty string), unknown key, exact timestamp match, queries earlier than the first set.
pythonfrom bisect import bisect_right from collections import defaultdict class TimeMap: def __init__(self): self.ts = defaultdict(list) self.vs = defaultdict(list) def set(self, key, value, timestamp): self.ts[key].append(timestamp) self.vs[key].append(value) def get(self, key, timestamp): i = bisect_right(self.ts[key], timestamp) return self.vs[key][i - 1] if i else ''javaclass TimeMap { private final Map<String, List<Integer>> ts = new HashMap<>(); private final Map<String, List<String>> vs = new HashMap<>(); void set(String key, String value, int timestamp) { ts.computeIfAbsent(key, k -> new ArrayList<>()).add(timestamp); vs.computeIfAbsent(key, k -> new ArrayList<>()).add(value); } String get(String key, int timestamp) { List<Integer> t = ts.get(key); if (t == null) return ""; int lo = 0, hi = t.size(); while (lo < hi) { int mid = (lo + hi) >>> 1; if (t.get(mid) <= timestamp) lo = mid + 1; else hi = mid; } return lo == 0 ? "" : vs.get(key).get(lo - 1); } }8 Hit counter: hits in the last 300 seconds
mediumHits arrive with non-decreasing timestamps. Keep a queue of timestamps. To count, drop timestamps from the front that are 300 or more seconds old, and return the queue size. For very heavy traffic, use 300 circular buckets with a timestamp each, giving O(1) space per window. Time amortised O(1) per call, space O(hits in the window). Edge cases: several hits at the same second, a query long after the last hit (returns 0), the window boundary (exactly 300 seconds old is excluded).
pythonfrom collections import deque class HitCounter: def __init__(self): self.q = deque() def hit(self, t): self.q.append(t) def get_hits(self, t): while self.q and self.q[0] <= t - 300: self.q.popleft() return len(self.q)javaclass HitCounter { private final Deque<Integer> q = new ArrayDeque<>(); void hit(int t) { q.add(t); } int getHits(int t) { while (!q.isEmpty() && q.peek() <= t - 300) q.poll(); return q.size(); } }9 Design a circular queue with a fixed array
mediumKeep an array of size k, a head index and a count. Enqueue writes at (head + count) % k and fails if full. Dequeue advances head modulo k and decrements the count. Tracking the count, not a tail index, removes the ambiguity between empty and full. Time O(1) per operation, space O(k). Edge cases: enqueue on a full queue and dequeue on an empty queue (return false), wraparound after many operations, capacity 1.
pythonclass MyCircularQueue: def __init__(self, k): self.a, self.k = [0] * k, k self.head = self.count = 0 def en_queue(self, v): if self.count == self.k: return False self.a[(self.head + self.count) % self.k] = v self.count += 1 return True def de_queue(self): if self.count == 0: return False self.head = (self.head + 1) % self.k self.count -= 1 return True def front(self): return -1 if self.count == 0 else self.a[self.head] def rear(self): return -1 if self.count == 0 else self.a[(self.head + self.count - 1) % self.k]javaclass MyCircularQueue { private final int[] a; private int head = 0, count = 0; MyCircularQueue(int k) { a = new int[k]; } boolean enQueue(int v) { if (count == a.length) return false; a[(head + count) % a.length] = v; count++; return true; } boolean deQueue() { if (count == 0) return false; head = (head + 1) % a.length; count--; return true; } int front() { return count == 0 ? -1 : a[head]; } int rear() { return count == 0 ? -1 : a[(head + count - 1) % a.length]; } }10 Snapshot array with cheap snapshots
mediumCopying the array on every snapshot is too costly. Store for each index a list of (snapshot id, value) pairs, appended only when that index changes. A get at snapshot s binary searches that index list for the last pair with id at most s. A snapshot just increments the counter. Time O(1) set and snap, O(log m) get, space O(number of sets). Edge cases: reading an index that was never set (0), setting the same index twice within one snapshot (overwrite the last pair), reading an old snapshot id.
pythonfrom bisect import bisect_right class SnapshotArray: def __init__(self, length): self.hist = [[(0, 0)] for _ in range(length)] self.snap_id = 0 def set(self, i, v): h = self.hist[i] if h[-1][0] == self.snap_id: h[-1] = (self.snap_id, v) else: h.append((self.snap_id, v)) def snap(self): self.snap_id += 1 return self.snap_id - 1 def get(self, i, snap_id): h = self.hist[i] j = bisect_right(h, (snap_id, float('inf'))) - 1 return h[j][1]javaclass SnapshotArray { private final List<int[]>[] hist; private int snapId = 0; @SuppressWarnings("unchecked") SnapshotArray(int length) { hist = new List[length]; for (int i = 0; i < length; i++) { hist[i] = new ArrayList<>(); hist[i].add(new int[]{0, 0}); } } void set(int i, int v) { List<int[]> h = hist[i]; if (h.get(h.size() - 1)[0] == snapId) h.get(h.size() - 1)[1] = v; else h.add(new int[]{snapId, v}); } int snap() { return snapId++; } int get(int i, int id) { List<int[]> h = hist[i]; int lo = 0, hi = h.size() - 1; while (lo < hi) { int mid = (lo + hi + 1) >>> 1; if (h.get(mid)[0] <= id) lo = mid; else hi = mid - 1; } return h.get(lo)[1]; } }11 Token bucket rate limiter
mediumA bucket holds up to capacity tokens and refills at a fixed rate. A request is allowed if at least one token is available, which it consumes. Instead of a timer, refill lazily on each call: tokens = min(capacity, tokens + elapsed * rate). It permits bursts up to the capacity while holding the long-run rate. Time O(1) per request, space O(1) per client (O(clients) overall). Edge cases: the first request (bucket starts full), time going backwards (clamp elapsed to 0), fractional tokens, one bucket per user or key, thread safety for concurrent use.
pythonclass TokenBucket: def __init__(self, capacity, rate_per_sec): self.cap, self.rate = capacity, rate_per_sec self.tokens, self.last = float(capacity), None def allow(self, now): if self.last is not None: self.tokens = min(self.cap, self.tokens + max(0.0, now - self.last) * self.rate) self.last = now if self.tokens >= 1: self.tokens -= 1 return True return Falsejavaclass TokenBucket { private final double cap, rate; private double tokens; private double last = Double.NaN; TokenBucket(double capacity, double ratePerSec) { cap = capacity; rate = ratePerSec; tokens = capacity; } synchronized boolean allow(double nowSec) { if (!Double.isNaN(last)) tokens = Math.min(cap, tokens + Math.max(0, nowSec - last) * rate); last = nowSec; if (tokens >= 1) { tokens -= 1; return true; } return false; } }12 All O(1) data structure: increment, decrement, get max and min key
hardEach key has a count. Keep a doubly linked list of buckets ordered by count, where each bucket holds the set of keys with that count, plus a map from key to its bucket. Incrementing moves a key to the bucket for count + 1, creating it next to the current one when needed. Decrementing moves it to count - 1 or removes it at 0. Empty buckets are unlinked. The max and min keys come from the tail and head buckets. Time O(1) per operation, space O(n). Edge cases: decrementing to zero removes the key, getMax on an empty structure (empty string), creating adjacent buckets in the right place, ties between keys with the same count (any is fine).
pythonclass Bucket: def __init__(self, cnt): self.cnt, self.keys, self.prev, self.next = cnt, set(), None, None class AllOne: def __init__(self): self.head, self.tail = Bucket(0), Bucket(0) self.head.next, self.tail.prev = self.tail, self.head self.where = {} def _insert_after(self, b, cnt): nb = Bucket(cnt) nb.prev, nb.next = b, b.next b.next.prev = nb b.next = nb return nb def _drop_if_empty(self, b): if not b.keys: b.prev.next, b.next.prev = b.next, b.prev def inc(self, key): if key not in self.where: nxt = self.head.next b = nxt if nxt.cnt == 1 else self._insert_after(self.head, 1) b.keys.add(key); self.where[key] = b return cur = self.where[key] nxt = cur.next b = nxt if nxt.cnt == cur.cnt + 1 and nxt is not self.tail else self._insert_after(cur, cur.cnt + 1) b.keys.add(key); self.where[key] = b cur.keys.discard(key); self._drop_if_empty(cur) def dec(self, key): if key not in self.where: return cur = self.where[key] cur.keys.discard(key) if cur.cnt == 1: del self.where[key] else: prv = cur.prev b = prv if prv.cnt == cur.cnt - 1 and prv is not self.head else self._insert_after(prv, cur.cnt - 1) b.keys.add(key); self.where[key] = b self._drop_if_empty(cur) def get_max(self): return next(iter(self.tail.prev.keys)) if self.tail.prev is not self.head else '' def get_min(self): return next(iter(self.head.next.keys)) if self.head.next is not self.tail else ''javaclass AllOne { private static class Bucket { int cnt; Set<String> keys = new HashSet<>(); Bucket prev, next; Bucket(int c) { cnt = c; } } private final Bucket head = new Bucket(0), tail = new Bucket(0); private final Map<String, Bucket> where = new HashMap<>(); AllOne() { head.next = tail; tail.prev = head; } private Bucket insertAfter(Bucket b, int cnt) { Bucket nb = new Bucket(cnt); nb.prev = b; nb.next = b.next; b.next.prev = nb; b.next = nb; return nb; } private void dropIfEmpty(Bucket b) { if (b.keys.isEmpty()) { b.prev.next = b.next; b.next.prev = b.prev; } } void inc(String key) { Bucket cur = where.get(key); Bucket b; if (cur == null) { b = head.next.cnt == 1 && head.next != tail ? head.next : insertAfter(head, 1); } else { b = cur.next != tail && cur.next.cnt == cur.cnt + 1 ? cur.next : insertAfter(cur, cur.cnt + 1); } b.keys.add(key); where.put(key, b); if (cur != null) { cur.keys.remove(key); dropIfEmpty(cur); } } void dec(String key) { Bucket cur = where.get(key); if (cur == null) return; cur.keys.remove(key); if (cur.cnt == 1) where.remove(key); else { Bucket b = cur.prev != head && cur.prev.cnt == cur.cnt - 1 ? cur.prev : insertAfter(cur.prev, cur.cnt - 1); b.keys.add(key); where.put(key, b); } dropIfEmpty(cur); } String getMax() { return tail.prev == head ? "" : tail.prev.keys.iterator().next(); } String getMin() { return head.next == tail ? "" : head.next.keys.iterator().next(); } }
Frequently asked questions
Why does an LRU cache need both a hash map and a linked list?
The map provides O(1) lookup of a key, and the doubly linked list provides O(1) move-to-front and removal of the oldest item. Either alone makes one of the operations O(n).
What is the difference between LRU and LFU?
LRU evicts the entry unused for the longest time. LFU evicts the entry used the fewest times, breaking ties by recency. LFU needs frequency buckets and a minimum frequency pointer.
How do I delete from an array in O(1)?
If order does not matter, swap the element with the last one, update any index map, then pop the end. This is how randomized set achieves O(1) delete.
Do design data structure questions appear in coding rounds?
LRU cache, min stack and randomized set are very common. The technical interview guide describes how such questions fit into a round.
Related guides
More in DSA Interview Questions
- Math and number theory interview questions with solutions
- Matrix interview questions with worked solutions
- Merge intervals pattern questions with worked solutions
- Minimum Spanning Tree Interview Questions
- Monotonic stack interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Queue and deque interview questions with worked solutions
- Recursion interview questions with worked solutions
- Segment Tree Interview Questions
- Sliding window interview questions with worked solutions
- Sorting algorithm interview questions with worked solutions
- Stack interview questions with worked solutions