Design problems are a special breed of interview questions. Instead of solving a puzzle with existing data structures, we’re asked to build a data structure that supports specific operations with specific time complexities. They test whether we truly understand how data structures work under the hood.
In simple language, the interviewer says “build me a thing that does X in O(1)” and we figure out which building blocks to combine.
Why Interviewers Love These
Design problems test multiple skills at once: understanding of data structures, ability to combine them creatively, edge case handling, and clean API design. They’re also closer to real engineering work — we often need to design custom data structures to meet performance requirements.
Min Stack
We covered this briefly in the stacks topic. Let’s go deeper. The challenge: design a stack that supports push, pop, top, and getMin — all in O(1) time.
The trick: maintain a second stack that tracks the minimum at each level. Every time we push to the main stack, we also track what the minimum is at that point.
A cleaner approach: store pairs of (value, current_minimum) in a single stack.
// Min Stack -- all operations O(1)
class MinStack {
constructor() {
this.stack = []; // each entry: [value, minAtThisLevel]
}
push(val) {
const currentMin = this.stack.length
? Math.min(val, this.getMin())
: val;
this.stack.push([val, currentMin]);
}
pop() {
this.stack.pop();
}
top() {
return this.stack[this.stack.length - 1][0];
}
getMin() {
return this.stack[this.stack.length - 1][1];
}
}# Min Stack -- all operations O(1)
class MinStack:
def __init__(self):
self.stack = [] # each entry: (value, min_at_this_level)
def push(self, val):
current_min = min(val, self.get_min()) if self.stack else val
self.stack.append((val, current_min))
def pop(self):
self.stack.pop()
def top(self):
return self.stack[-1][0]
def get_min(self):
return self.stack[-1][1]// Min Stack -- all operations O(1)
class MinStack {
// each entry: [value, minAtThisLevel]
Deque<int[]> stack = new ArrayDeque<>();
void push(int val) {
int currentMin = stack.isEmpty() ? val : Math.min(val, getMin());
stack.push(new int[]{val, currentMin});
}
void pop() { stack.pop(); }
int top() { return stack.peek()[0]; }
int getMin() { return stack.peek()[1]; }
}The space trade-off is O(n) extra for the minimums. That’s acceptable — we traded space for O(1) getMin.
Queue Using Two Stacks
Design a queue (FIFO) using only two stacks. This sounds weird, but it’s a common interview question that tests our understanding of both structures.
The idea: use one stack for pushing (inStack) and one for popping (outStack). When we need to dequeue and outStack is empty, we pour everything from inStack into outStack. This reverses the order — and reversing LIFO gives us FIFO.
Each element gets moved at most twice (pushed to inStack, moved to outStack), so amortized cost per operation is O(1).
// Queue using two stacks -- amortized O(1) per operation
class MyQueue {
constructor() {
this.inStack = []; // for push
this.outStack = []; // for pop/peek
}
push(val) {
this.inStack.push(val);
}
pop() {
this._transfer();
return this.outStack.pop();
}
peek() {
this._transfer();
return this.outStack[this.outStack.length - 1];
}
empty() {
return !this.inStack.length && !this.outStack.length;
}
_transfer() {
// only transfer when outStack is empty
if (!this.outStack.length) {
while (this.inStack.length) {
this.outStack.push(this.inStack.pop());
}
}
}
}# Queue using two stacks -- amortized O(1) per operation
class MyQueue:
def __init__(self):
self.in_stack = [] # for push
self.out_stack = [] # for pop/peek
def push(self, val):
self.in_stack.append(val)
def pop(self):
self._transfer()
return self.out_stack.pop()
def peek(self):
self._transfer()
return self.out_stack[-1]
def empty(self):
return not self.in_stack and not self.out_stack
def _transfer(self):
# only transfer when out_stack is empty
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())// Queue using two stacks -- amortized O(1) per operation
class MyQueue {
Deque<Integer> inStack = new ArrayDeque<>();
Deque<Integer> outStack = new ArrayDeque<>();
void push(int val) { inStack.push(val); }
int pop() { transfer(); return outStack.pop(); }
int peek() { transfer(); return outStack.peek(); }
boolean empty() { return inStack.isEmpty() && outStack.isEmpty(); }
private void transfer() {
if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
}
}LRU Cache — The Big One
Design a cache with a fixed capacity that evicts the Least Recently Used item when full. It needs:
get(key)— return the value in O(1), mark as recently usedput(key, value)— insert/update in O(1), evict LRU if over capacity
This is probably the most commonly asked design problem. Let’s build it.
The Insight
We need two things working together:
- Hash map for O(1) key lookup
- Doubly linked list for O(1) insertion/removal and tracking recency order
The most recently used item goes to the front of the list. The least recently used is at the back. When we access or insert an item, we move it to the front. When we need to evict, we remove from the back.
We use sentinel head and tail nodes to avoid null checks. Every real node sits between them.
Full Implementation
// LRU Cache -- O(1) get and put
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map();
// sentinel nodes -- avoid null checks
this.head = { prev: null, next: null };
this.tail = { prev: null, next: null };
this.head.next = this.tail;
this.tail.prev = this.head;
}
get(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this._remove(node);
this._addToFront(node);
return node.val;
}
put(key, value) {
if (this.map.has(key)) {
this._remove(this.map.get(key));
}
const node = { key, val: value, prev: null, next: null };
this._addToFront(node);
this.map.set(key, node);
if (this.map.size > this.capacity) {
const lru = this.tail.prev; // least recently used
this._remove(lru);
this.map.delete(lru.key);
}
}
_remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
_addToFront(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
}# LRU Cache -- O(1) get and put
class DLLNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.map = {}
# sentinel nodes -- avoid null checks
self.head = DLLNode()
self.tail = DLLNode()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key):
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_to_front(node)
return node.val
def put(self, key, value):
if key in self.map:
self._remove(self.map[key])
node = DLLNode(key, value)
self._add_to_front(node)
self.map[key] = node
if len(self.map) > self.capacity:
lru = self.tail.prev # least recently used
self._remove(lru)
del self.map[lru.key]
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node// LRU Cache -- O(1) get and put
class LRUCache {
class DLLNode {
int key, val;
DLLNode prev, next;
DLLNode(int k, int v) { key = k; val = v; }
}
int capacity;
Map<Integer, DLLNode> map = new HashMap<>();
DLLNode head = new DLLNode(0, 0); // sentinel
DLLNode tail = new DLLNode(0, 0); // sentinel
LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
int get(int key) {
if (!map.containsKey(key)) return -1;
DLLNode node = map.get(key);
remove(node);
addToFront(node);
return node.val;
}
void put(int key, int value) {
if (map.containsKey(key)) remove(map.get(key));
DLLNode node = new DLLNode(key, value);
addToFront(node);
map.put(key, node);
if (map.size() > capacity) {
DLLNode lru = tail.prev;
remove(lru);
map.remove(lru.key);
}
}
void remove(DLLNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
void addToFront(DLLNode node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
}Python Shortcut
Python’s OrderedDict maintains insertion order and supports move_to_end. This makes LRU cache a 10-line solution:
# LRU Cache using OrderedDict -- Python shortcut
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key) # mark as recently used
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # remove oldest (LRU)Know both approaches. The OrderedDict version is great for speed in interviews, but the interviewer might ask us to implement it from scratch.
Java Shortcut
Java’s LinkedHashMap maintains insertion order too:
// LRU Cache using LinkedHashMap -- Java shortcut
class LRUCache extends LinkedHashMap<Integer, Integer> {
int capacity;
LRUCache(int capacity) {
super(capacity, 0.75f, true); // true = access-order
this.capacity = 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> eldest) {
return size() > capacity; // auto-evict when over capacity
}
}Tips for Design Problems in Interviews
- Clarify requirements first. What operations? What time complexities? What constraints?
- Start with the brute force. “We could use a list and scan it each time, but that’s O(n)…”
- Identify the bottleneck. Which operation is too slow? What data structure speeds it up?
- Combine data structures. The magic is usually in combining two simple structures (hash map + linked list, two stacks, etc.).
- Handle edge cases. Empty state, single element, at capacity. The interviewer will ask about these.
Design problems feel intimidating, but they all follow the same pattern: figure out what’s slow, pick the right data structure to fix it, and combine structures when one isn’t enough.