Design Problems

Design problems ask you to implement a data structure with specific operation constraints — usually O(1) or amortized O(1) time. These are common at FAANG interviews because they test whether you can combine simpler structures to achieve better overall complexity.

Min Stack — O(1) getMin

Design a stack that supports push, pop, top, and getMin in O(1). The challenge: removing an element might change the minimum. We solve this with an auxiliary stack that tracks the running minimum.

class MinStack {
  private stack: number[] = [];
  private minStack: number[] = [];  // tracks minimum at each stack level

  push(val: number): void {
    this.stack.push(val);
    // Push min(val, current min) — ties are fine and important
    const currentMin = this.minStack.length
      ? this.minStack[this.minStack.length - 1]
      : Infinity;
    this.minStack.push(Math.min(val, currentMin));
  }

  pop(): void {
    this.stack.pop();
    this.minStack.pop();  // remove corresponding minimum
  }

  top(): number {
    return this.stack[this.stack.length - 1];
  }

  getMin(): number {
    return this.minStack[this.minStack.length - 1];
  }
}

const ms = new MinStack();
ms.push(3);
ms.push(5);
ms.push(2);
ms.push(4);
console.log(ms.getMin()); // 2
ms.pop();                  // remove 4
ms.pop();                  // remove 2
console.log(ms.getMin()); // 3  ← correctly recovered

Note

The auxiliary minStack grows and shrinks in sync with the main stack. After pop(), the previous minimum is already sitting at the top of minStack — no recomputation needed.

Max Stack

The same pattern applies for maximum. Track the running maximum alongside the main stack.

class MaxStack {
  private stack: number[] = [];
  private maxStack: number[] = [];

  push(val: number): void {
    this.stack.push(val);
    const currentMax = this.maxStack.length
      ? this.maxStack[this.maxStack.length - 1]
      : -Infinity;
    this.maxStack.push(Math.max(val, currentMax));
  }

  pop(): number {
    this.maxStack.pop();
    return this.stack.pop()!;
  }

  peekMax(): number {
    return this.maxStack[this.maxStack.length - 1];
  }
}

Queue Using Two Stacks — Amortized O(1)

A queue is FIFO; a stack is LIFO. Use two stacks: inbox receives push operations, outbox serves pop/peek. When outbox is empty, pour all of inbox into outbox (reversing the order).

Each element moves from inbox to outbox exactly once, giving amortized O(1) per operation.

// LeetCode 232 — Implement Queue using Stacks
class MyQueue {
  private inbox: number[] = [];   // push here
  private outbox: number[] = [];  // pop/peek from here

  push(x: number): void {
    this.inbox.push(x);
  }

  pop(): number {
    this.refill();
    return this.outbox.pop()!;
  }

  peek(): number {
    this.refill();
    return this.outbox[this.outbox.length - 1];
  }

  empty(): boolean {
    return this.inbox.length === 0 && this.outbox.length === 0;
  }

  private refill(): void {
    if (this.outbox.length === 0) {
      while (this.inbox.length > 0) {
        this.outbox.push(this.inbox.pop()!);
      }
    }
  }
}

const q = new MyQueue();
q.push(1); q.push(2); q.push(3);
console.log(q.pop());   // 1  (FIFO)
console.log(q.peek());  // 2

Stack Using Two Queues

// LeetCode 225 — Implement Stack using Queues
class MyStack {
  private q1: number[] = [];
  private q2: number[] = [];

  push(x: number): void {
    this.q2.push(x);
    // Move all of q1 behind x
    while (this.q1.length > 0) this.q2.push(this.q1.shift()!);
    [this.q1, this.q2] = [this.q2, this.q1];  // swap: q1 now holds elements in LIFO order
  }

  pop(): number {
    return this.q1.shift()!;
  }

  top(): number {
    return this.q1[0];
  }

  empty(): boolean {
    return this.q1.length === 0;
  }
}

const s = new MyStack();
s.push(1); s.push(2); s.push(3);
console.log(s.top());  // 3
console.log(s.pop());  // 3
console.log(s.top());  // 2

Design HashMap — Open Addressing with Chaining

Implement a HashMap from scratch without using built-in hash table structures. Use an array of buckets where each bucket holds a linked list of (key, value) pairs to handle collisions (chaining).

// LeetCode 706 — Design HashMap
class MyHashMap {
  private static readonly SIZE = 1009;  // prime number reduces clustering
  private buckets: Array<Array<[number, number]>>;

  constructor() {
    this.buckets = Array.from({ length: MyHashMap.SIZE }, () => []);
  }

  private hash(key: number): number {
    return key % MyHashMap.SIZE;
  }

  put(key: number, value: number): void {
    const bucket = this.buckets[this.hash(key)];
    const entry = bucket.find(([k]) => k === key);
    if (entry) entry[1] = value;
    else bucket.push([key, value]);
  }

  get(key: number): number {
    const bucket = this.buckets[this.hash(key)];
    const entry = bucket.find(([k]) => k === key);
    return entry ? entry[1] : -1;
  }

  remove(key: number): void {
    const h = this.hash(key);
    this.buckets[h] = this.buckets[h].filter(([k]) => k !== key);
  }
}

const map = new MyHashMap();
map.put(1, 1); map.put(2, 2);
console.log(map.get(1));   // 1
console.log(map.get(3));   // -1
map.put(2, 1);
console.log(map.get(2));   // 1
map.remove(2);
console.log(map.get(2));   // -1

Design HashSet

// LeetCode 705 — Design HashSet
class MyHashSet {
  private static readonly SIZE = 1009;
  private buckets: Array<number[]>;

  constructor() {
    this.buckets = Array.from({ length: MyHashSet.SIZE }, () => []);
  }

  private hash(key: number): number {
    return key % MyHashSet.SIZE;
  }

  add(key: number): void {
    const bucket = this.buckets[this.hash(key)];
    if (!bucket.includes(key)) bucket.push(key);
  }

  remove(key: number): void {
    const h = this.hash(key);
    this.buckets[h] = this.buckets[h].filter(k => k !== key);
  }

  contains(key: number): boolean {
    return this.buckets[this.hash(key)].includes(key);
  }
}

Randomized Set — O(1) Insert / Delete / GetRandom

Design a set supporting insert, remove, and getRandom (each element equally likely) all in O(1). This is the hardest of the bunch. The trick: store elements in a dynamic array for O(1) random access, and use a HashMap from value → array index for O(1) lookup and O(1) removal.

Removal trick: swap the target with the last element, update the map, then pop the array.

// LeetCode 380 — Insert Delete GetRandom O(1)
class RandomizedSet {
  private vals: number[] = [];                    // array for O(1) random access
  private indexMap = new Map<number, number>();   // value → index in vals

  insert(val: number): boolean {
    if (this.indexMap.has(val)) return false;
    this.vals.push(val);
    this.indexMap.set(val, this.vals.length - 1);
    return true;
  }

  remove(val: number): boolean {
    if (!this.indexMap.has(val)) return false;
    const idx = this.indexMap.get(val)!;
    const last = this.vals[this.vals.length - 1];
    // Swap val with last element
    this.vals[idx] = last;
    this.indexMap.set(last, idx);
    // Remove last
    this.vals.pop();
    this.indexMap.delete(val);
    return true;
  }

  getRandom(): number {
    const idx = Math.floor(Math.random() * this.vals.length);
    return this.vals[idx];
  }
}

const rs = new RandomizedSet();
rs.insert(1); rs.insert(2); rs.insert(3);
rs.remove(2);
// getRandom returns 1 or 3 with equal probability
console.log(rs.getRandom()); // 1 or 3

Note

The swap-with-last trick is the key to O(1) removal from an unsorted array. Without it, removing an element from the middle requires shifting, which is O(n). The map lets us find the index in O(1) and update it after the swap in O(1).

Summary

Problem	Key structures	All operations
Min/Max Stack	Stack + auxiliary stack	O(1)
Queue using 2 Stacks	Two stacks (inbox + outbox)	Amortized O(1)
Stack using 2 Queues	Two queues (rotate on push)	O(n) push, O(1) pop
Design HashMap	Array of buckets + chaining	O(1) avg / O(n) worst
Design HashSet	Array of buckets + chaining	O(1) avg / O(n) worst
Randomized Set	Array + HashMap (value→index)	O(1) all operations
LRU Cache	HashMap + Doubly Linked List	O(1) get and put

Tip

For every design problem, start by listing the operations and their required complexities. Then ask: which structure gives me O(1) lookup? (HashMap) Which gives O(1) at both ends? (Deque) Which gives O(1) random access? (Array) Often the answer is a combination of two.