Design problems

These questions are graded on the choice, not the code

"Design an LRU cache with O(1) get and put." "Design a stack with O(1) getMin." The implementation is usually forty lines of unremarkable pointer-juggling. What's being tested is the twenty seconds before that: can you read a set of required operations and their required complexities, notice that no single data structure delivers all of them, and compose two structures where each covers the other's blind spot?

The universal opening move: write the operation table first. Every operation, its required complexity, and the structure that provides it. Do this out loud, on the board, before touching code.

LRU cache: the canonical composition

The contract: get(key) and put(key, value), both O(1), with the least-recently-used entry evicted when capacity is exceeded. A hash map gives O(1) lookup but has no notion of "oldest." An array or list gives ordering, but finding a key in it is O(n). A doubly linked list gives O(1) removal if you already hold the node — which is exactly what the map can hand you.

// LRU cache — get, put, and eviction all O(1). O(capacity) space.
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map(); // key → node reference (NOT key → value)

    // sentinel head/tail remove every null check from the unlink code
    this.head = { key: null, val: null, prev: null, next: null };
    this.tail = { key: null, val: null, prev: null, next: null };
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  _unlink(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  _pushFront(node) { // front (next to head) = most recently used
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    const node = this.map.get(key);
    if (!node) return -1;
    this._unlink(node);
    this._pushFront(node); // a read counts as a use — this is the line people forget
    return node.val;
  }

  put(key, value) {
    const existing = this.map.get(key);
    if (existing) {
      existing.val = value;
      this._unlink(existing);
      this._pushFront(existing);
      return; // an update must NOT evict anything
    }

    if (this.map.size === this.cap) {
      const lru = this.tail.prev;
      this._unlink(lru);
      this.map.delete(lru.key); // why nodes store their key: you evict from the list, delete from the map
    }

    const node = { key, val: value, prev: null, next: null };
    this._pushFront(node);
    this.map.set(key, node);
  }
}

Worth mentioning after you've written the real thing: JavaScript's Map preserves insertion order, so map.delete(k); map.set(k, v); moves a key to the back, and map.keys().next().value is the oldest key — a ten-line LRU. Say it as a language-specific shortcut you know about, then note that interviewers ask this question precisely to see the linked-list mechanics, so you'd hand-roll it here.

LFU cache: the same trick, one level deeper

LFU evicts the least frequently used entry, breaking ties by least-recently used. Now three things must be O(1): find a key, find the minimum frequency, and find the oldest key at that frequency. The answer is to bucket by frequency and keep each bucket internally ordered — a map from count to an ordered collection of keys — plus a single minFreq integer.

Why a bare minFreq counter is enough is the elegant part: frequencies only ever increase by exactly 1. So minFreq can only rise by 1 (when the last key in the minimum bucket is promoted) or reset to 1 (when a brand-new key is inserted). You never have to search for the new minimum.

// LFU — get/put O(1). A JS Set preserves insertion order, so it doubles as
// the per-bucket LRU list; in another language this is a DLL per bucket.
class LFUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.vals = new Map();    // key → value
    this.freq = new Map();    // key → use count
    this.buckets = new Map(); // count → Set of keys, oldest first
    this.minFreq = 0;
  }

  _promote(key) {
    const f = this.freq.get(key);
    const bucket = this.buckets.get(f);
    bucket.delete(key);
    if (bucket.size === 0) {
      this.buckets.delete(f);
      if (this.minFreq === f) this.minFreq++; // safe: counts only ever step up by 1
    }
    this.freq.set(key, f + 1);
    if (!this.buckets.has(f + 1)) this.buckets.set(f + 1, new Set());
    this.buckets.get(f + 1).add(key);
  }

  get(key) {
    if (!this.vals.has(key)) return -1;
    this._promote(key);
    return this.vals.get(key);
  }

  put(key, value) {
    if (this.cap === 0) return;
    if (this.vals.has(key)) { this.vals.set(key, value); this._promote(key); return; }

    if (this.vals.size === this.cap) {
      const victims = this.buckets.get(this.minFreq);
      const victim = victims.values().next().value; // oldest key in the least-used bucket → LRU tiebreak
      victims.delete(victim);
      if (victims.size === 0) this.buckets.delete(this.minFreq);
      this.vals.delete(victim);
      this.freq.delete(victim);
    }

    this.vals.set(key, value);
    this.freq.set(key, 1);
    if (!this.buckets.has(1)) this.buckets.set(1, new Set());
    this.buckets.get(1).add(key);
    this.minFreq = 1; // a fresh key always resets the minimum
  }
}

Note the shape is identical to LRU — a lookup structure pointing into an ordered structure — just nested one level: map → bucket → ordered keys. If you can explain LRU cleanly, LFU is a five-sentence extension, and saying "it's LRU with a frequency dimension, and minFreq works because counts only increment" is usually enough to satisfy the follow-up.

Min stack: O(1) getMin with an auxiliary stack

The trap is reaching for a heap. A heap gives O(log n) min with arbitrary removal — but a stack doesn't have arbitrary removal. Pops happen in exactly the reverse order of pushes, which means you can precompute the answer: at push time, record the minimum of everything at or below this point. Popping automatically restores the previous minimum because you pop that record too.

// push / pop / top / getMin all O(1). O(n) extra space.
class MinStack {
  constructor() {
    this.main = [];
    this.mins = []; // mins[i] = min of main[0..i] — a running prefix minimum
  }

  push(x) {
    this.main.push(x);
    const currentMin = this.mins.length ? this.mins[this.mins.length - 1] : x;
    this.mins.push(Math.min(x, currentMin));
  }

  pop() {
    this.mins.pop(); // discarding this entry restores the previous min for free
    return this.main.pop();
  }

  top()    { return this.main[this.main.length - 1]; }
  getMin() { return this.mins[this.mins.length - 1]; }
}

The space optimization interviewers like to fish for: only push to mins when the new value is a new minimum, and only pop from it when the popped value equals the current minimum.

  push(x) {
    this.main.push(x);
    if (!this.mins.length || x <= this.mins[this.mins.length - 1]) this.mins.push(x);
  }

  pop() {
    const x = this.main.pop();
    if (x === this.mins[this.mins.length - 1]) this.mins.pop();
    return x;
  }

Max Stack is the same design for peekMax(). But if the question also demands popMax() — remove the maximum from anywhere in the stack — the auxiliary-stack trick breaks, because you're no longer popping in reverse push order. That version needs a doubly linked list plus an ordered map from value to the list of nodes holding it, giving O(log n) popMax. Naming that boundary unprompted ("this trick works only because removals are LIFO") is the senior-level version of this answer.

Hit counter: designing for a stream

"Count hits in the last 5 minutes, with timestamps arriving in non-decreasing order." The naive store-everything approach is O(1) per hit but unbounded memory. The complexity contract to negotiate here isn't just time — it's space, and the interviewer is waiting for you to notice that the window is fixed-size.

// Version 1: a queue of timestamps. O(1) amortized hit, O(1) amortized
// getHits, but O(hits) space — unbounded under load.
class HitCounter {
  constructor(windowSec = 300) {
    this.window = windowSec;
    this.times = [];
    this.head = 0; // head pointer instead of shift() — shift() is O(n)
  }

  hit(ts) { this.times.push(ts); }

  getHits(ts) {
    while (this.head < this.times.length && this.times[this.head] <= ts - this.window) {
      this.head++; // each timestamp is skipped at most once across all calls
    }
    return this.times.length - this.head;
  }
}

// Version 2: a ring buffer of per-second buckets. O(1) hit, O(window)
// getHits, and O(window) space no matter the traffic — the one to ship.
class BucketedHitCounter {
  constructor(windowSec = 300) {
    this.n = windowSec;
    this.stamps = new Array(windowSec).fill(-1); // which second this slot currently represents
    this.counts = new Array(windowSec).fill(0);
  }

  hit(ts) {
    const i = ts % this.n;
    if (this.stamps[i] !== ts) {         // slot belongs to an older second — reuse it
      this.stamps[i] = ts;
      this.counts[i] = 1;
    } else {
      this.counts[i]++;
    }
  }

  getHits(ts) {
    let total = 0;
    for (let i = 0; i < this.n; i++) {
      if (ts - this.stamps[i] < this.n) total += this.counts[i]; // skip stale slots without clearing them
    }
    return total;
  }
}

The lazy-expiry idea — never clear old data, just check whether a slot's timestamp is still in range when you read it — is the reusable insight here. It's the same technique behind lazy deletion in heaps and tombstones in log-structured storage.

Rate limiter: a sliding window counter

The natural follow-up, and the one that bridges into system design. A fixed-window counter is trivial but lets a client fire 2× the limit across a window boundary. Storing every request timestamp is exact but O(limit) memory per user. The sliding-window-counter approximation keeps two integers per user and weights the previous window by how much of it still overlaps — the algorithm real API gateways ship.

// O(1) time and O(1) space PER USER. Approximate, but bounded error.
class SlidingWindowRateLimiter {
  constructor(limit, windowMs) {
    this.limit = limit;
    this.windowMs = windowMs;
    this.state = new Map(); // userId → { start, count, prevCount }
  }

  allow(userId, now = Date.now()) {
    const start = Math.floor(now / this.windowMs) * this.windowMs;
    let s = this.state.get(userId);

    if (!s || s.start < start - this.windowMs) {
      s = { start, count: 0, prevCount: 0 }; // idle for 2+ windows — everything expired
    } else if (s.start < start) {
      s = { start, count: 0, prevCount: s.count }; // rolled into a new window: demote count
    }
    this.state.set(userId, s);

    // fraction of the previous window still inside the trailing window
    const overlap = 1 - (now - start) / this.windowMs;
    const estimate = s.prevCount * overlap + s.count;

    if (estimate >= this.limit) return false;
    s.count++;
    return true;
  }
}

How to run the first two minutes of any design question

Steps 1-5 take ninety seconds and are where the hiring signal lives. A candidate who writes a flawless LRU without ever explaining why the list must be doubly linked has demonstrated recall; a candidate who derives it from "unlink must be O(1) and I only hold the node, not its predecessor" has demonstrated design.

Recognizing it in an unseen problem

• The prompt starts with the word "Design" and hands you a class signature with named methods and stated complexities — the complexities are the problem statement
• Two operations pull in opposite directions: fast lookup versus maintained order, or fast insert versus fast min/max. That tension is the signal to compose two structures rather than search for one perfect one
• Something must be evicted, expired, or capped — look for hash map + doubly linked list (recency), frequency buckets (LFU), or a ring buffer / deque (time windows)
• "O(1) min/max" on a structure with LIFO removal → auxiliary stack. "O(1) min/max" with arbitrary removal → you need a heap or ordered map, and the honest answer is O(log n), not O(1)
• "Streaming," "in the last N seconds," "timestamps arrive in order" → the window is fixed, so memory should be O(window), not O(events); bucket and expire lazily
• Distinguish from an algorithms question: there's no clever traversal or recurrence here. If you're searching for an algorithm, you've misread it — you're searching for a combination
• Pitfalls: forgetting that a read counts as a use, not storing the key inside the node so eviction can clean up the map, using < where <= is needed on duplicate minimums, and letting the per-key map grow without bound