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) {
    if (this.cap === 0) return; // nothing can be stored, so there is nothing to evict either
    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);
  }
}

Dry run: LRUCache(3) — the same keys as the figure above

The get("C") call is the pivot: before it, B was the newer entry and C was next in line for eviction. One read moves C to the front and leaves B stranded at the tail — B is evicted not because it was written first — C was written first and survives — but because nobody has touched it for the longest time. That's the entire meaning of "least recently used."

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.

All O(1): LFU's buckets, with the list made explicit

The contract: inc(key), dec(key), getMaxKey() and getMinKey(), all O(1). A map from key to count makes inc and dec trivial and says nothing about the largest or smallest count. A heap finds the extreme in O(1) but moving one key's count inside it costs O(log n), and sorting on every query costs far more. So the requirement is a structure that keeps counts in sorted order and survives a key changing its count.

The fact that makes it possible is the same one that powered minFreq in the LFU cache: a count changes by exactly 1. When a key moves from count c to c + 1, the only place it can belong in the sorted order is the bucket for c + 1 — which, if it exists, is already the next bucket in the list — or a brand-new bucket spliced in directly after the old one. There is never anything to search for. Keep one bucket per distinct count, each holding a Set of the keys with that count, link the buckets into a doubly linked list sorted by count, and give the map a handle to each key's bucket. The maximum is the last bucket and the minimum is the first.

class AllOne {
  constructor() {
    this.head = { count: 0, keys: new Set(), prev: null, next: null }; // sentinel: "count 0"
    this.tail = { count: Infinity, keys: new Set(), prev: null, next: null };
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.bucketOf = new Map(); // key -> the bucket that holds it
  }

  _insertAfter(node, count) {
    const bucket = { count, keys: new Set(), prev: node, next: node.next };
    node.next.prev = bucket;
    node.next = bucket;
    return bucket;
  }

  _unlinkIfEmpty(bucket) {
    if (bucket === this.head || bucket.keys.size > 0) return;
    bucket.prev.next = bucket.next;
    bucket.next.prev = bucket.prev;
  }

  inc(key) {
    const from = this.bucketOf.get(key) || this.head;
    const count = from.count + 1;
    const to = from.next.count === count ? from.next : this._insertAfter(from, count);
    to.keys.add(key);
    this.bucketOf.set(key, to);
    from.keys.delete(key);
    this._unlinkIfEmpty(from);
  }

  dec(key) {
    const from = this.bucketOf.get(key);
    if (!from) return;
    const count = from.count - 1;
    if (count === 0) {
      this.bucketOf.delete(key);
    } else {
      const to = from.prev.count === count ? from.prev : this._insertAfter(from.prev, count);
      to.keys.add(key);
      this.bucketOf.set(key, to);
    }
    from.keys.delete(key);
    this._unlinkIfEmpty(from);
  }

  getMaxKey() {
    return this.tail.prev === this.head ? "" : this.tail.prev.keys.values().next().value;
  }

  getMinKey() {
    return this.head.next === this.tail ? "" : this.head.next.keys.values().next().value;
  }
}

Dry run: the list of buckets, count : keys, after each call

Row 3 is the whole trick in one step: a leaves the 1-bucket, finds no 2-bucket next to it, and a fresh one is spliced in right after. Row 7 shows the cleanup: a drops to 1, joins the existing 1-bucket, and the 2-bucket it left behind is empty, so it is unlinked at once. Ties return whichever key the bucket's Set yields first; the contract allows any of them.

Every call touches at most three buckets (the old one, the new one, and a neighbour to compare counts with) and does a constant number of Set and Map operations, so each operation is O(1) on average, and the space is O(distinct keys). The two sentinels do real work: the tail's count of Infinity means from.next.count === count can never match it, and the head's count of 0 lets a brand-new key start from "count 0" through the same code path as every other increment.

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

The trap is reaching for a heap. A heap pays O(log n) per push and pop to support 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 or ties the current one, 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.

Time-based key-value store: a sorted history per key

set(key, value, timestamp) records a value; get(key, timestamp) returns the value that was in force at that moment, which is the one with the largest stored time that is at most the query. If nothing was written by then, the answer is the empty string. The naive design keeps every write in one global list and scans it: correct, and O(total writes) per get. The first fix is obvious: histories of different keys never interact, so give each key its own list.

The second fix is the one being tested. If timestamps arrive in increasing order, each key's list is already sorted by time, because appending is the only operation, so get can binary search instead of scanning. The detail that costs offers is the shape of that search. It is not "find this exact time"; it is "find the last version not after this time", the same boundary search as an upper bound: look for the first version written after the query, and the answer is the one just before it.

class TimeMap {
  constructor() {
    this.versions = new Map(); // key -> [[timestamp, value], ...], oldest first
  }

  set(key, value, timestamp) {
    if (!this.versions.has(key)) this.versions.set(key, []);
    this.versions.get(key).push([timestamp, value]); // timestamps only grow, so the list stays sorted
  }

  get(key, timestamp) {
    const list = this.versions.get(key);
    if (!list) return "";
    let lo = 0;
    let hi = list.length; // search for the first version written AFTER timestamp
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (list[mid][0] <= timestamp) lo = mid + 1;
      else hi = mid;
    }
    return lo === 0 ? "" : list[lo - 1][1]; // the version just before that one
  }
}

Dry run: three versions of one key, then get("k", 6)

After set("k","a",2), set("k","b",5) and set("k","c",9) the list is [(2,a), (5,b), (9,c)].

Other queries on the same list: time 1 gives "" (lo stays 0, so nothing is at or before it), time 5 gives "b" (an exact match counts, because the comparison is <=), and time 100 gives "c".

set is O(1) amortized and get is O(log m), where m is the number of versions of that one key, not of all keys. Memory is O(total writes), and nothing in this design ever deletes: say so, and say what you would add (a retention window, or compaction of old versions) if asked.

When timestamps can arrive out of order

The "increasing timestamps" promise is what keeps set a plain append. If a write can arrive with any timestamp, the list must be kept sorted by inserting at the position the same binary search finds, and a second write at an existing instant must replace the first rather than add a duplicate. In JavaScript the insert is a splice, which shifts the tail, so set becomes O(m); an ordered tree or skip list makes it O(log m), but JavaScript has no built-in ordered map, so that is a sentence to say, not code to write.

class TimeMapAnyOrder {
  constructor() {
    this.versions = new Map();
  }

  _after(list, timestamp) {
    let lo = 0;
    let hi = list.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (list[mid][0] <= timestamp) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }

  set(key, value, timestamp) {
    if (!this.versions.has(key)) this.versions.set(key, []);
    const list = this.versions.get(key);
    const at = this._after(list, timestamp);
    if (at > 0 && list[at - 1][0] === timestamp) list[at - 1][1] = value; // same instant: last write wins
    else list.splice(at, 0, [timestamp, value]); // splice shifts the tail: O(versions) per out-of-order write
  }

  get(key, timestamp) {
    const list = this.versions.get(key);
    if (!list) return "";
    const at = this._after(list, timestamp);
    return at === 0 ? "" : list[at - 1][1];
  }
}

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;
  }
}

Insert, delete, getRandom in O(1): a dense array with a map of positions

insert(v), remove(v) and getRandom(), all O(1) on average, where getRandom must return every current member with equal probability. Try the single structures first, because the failure of each one is the design. A Set inserts, removes and tests membership in O(1) but has no way to say "give me the member at a random position"; turning it into an array first costs O(n). An array picks a random position in O(1) but finds a value in O(n), and deleting from its middle shifts everything after it, also O(n).

Compose them, and attack the one thing that is still slow. Keep a dense array of the values, so a random index is a random member, and a Map from each value to its index in the array, so membership and "where is it" are O(1). Insert pushes onto the end and records the index. The remaining problem is removal from the middle. The key observation is that the array promises density, not order: nobody asked for the members in any particular sequence. So instead of shifting the tail left, move the last element into the hole and pop the end. One write, one pop, O(1).

class RandomizedSet {
  constructor() {
    this.values = []; // dense array: getRandom is an index
    this.slot = new Map(); // value -> its index in values
  }

  insert(value) {
    if (this.slot.has(value)) return false;
    this.slot.set(value, this.values.length);
    this.values.push(value);
    return true;
  }

  remove(value) {
    if (!this.slot.has(value)) return false;
    const hole = this.slot.get(value);
    const last = this.values[this.values.length - 1];
    this.values[hole] = last; // the last value fills the hole
    this.slot.set(last, hole); // ...and learns its new index
    this.values.pop();
    this.slot.delete(value); // LAST: when value === last, this undoes the set above
    return true;
  }

  getRandom() {
    return this.values[Math.floor(Math.random() * this.values.length)];
  }
}

Dry run: insert 10, 20, 30, 40, then remove 20, 40, 30

The last row is the case that breaks careless versions. When the value being removed is itself the last element, "move the last one into the hole" copies it onto itself, and the order of the final two lines of the method decides whether the map ends up correct.

With duplicates: a Set of positions per value

Now insert may add a copy of a value already present, remove removes one copy, and a value stored three times must be three times as likely to be returned. The array may now hold the same value at several indices, so the map's value must grow from one index to a Set of indices. Everything else is the same move: pick any index of the value being removed, fill that hole with the last element, and tell the last element's value that one of its positions changed.

class RandomizedCollection {
  constructor() {
    this.values = [];
    this.slots = new Map(); // value -> Set of every index where it sits in values
  }

  insert(value) {
    const isNew = !this.slots.has(value);
    if (isNew) this.slots.set(value, new Set());
    this.slots.get(value).add(this.values.length);
    this.values.push(value);
    return isNew; // true only for the first copy
  }

  remove(value) {
    const mine = this.slots.get(value);
    if (!mine) return false;
    const hole = mine.values().next().value; // any one copy will do
    const lastIndex = this.values.length - 1;
    const last = this.values[lastIndex];
    mine.delete(hole);
    if (hole !== lastIndex) {
      this.values[hole] = last;
      const theirs = this.slots.get(last); // when last === value this is the same Set as mine
      theirs.delete(lastIndex);
      theirs.add(hole);
    }
    this.values.pop();
    if (mine.size === 0) this.slots.delete(value);
    return true;
  }

  getRandom() {
    return this.values[Math.floor(Math.random() * this.values.length)];
  }
}

The comment on theirs marks the subtle case. If the last element is another copy of the value being removed, theirs and mine are the same Set: the code has already removed hole from it, then removes lastIndex and adds hole, which leaves exactly the right positions. Draws are proportional to count simply because each copy occupies one array slot. In one run of 60,000 draws from a collection holding 1, 1, 2, the value 1 came back 39,868 times, against 40,000 expected.

Complexity: insert, remove and getRandom are O(1) on average for both versions, since each does a constant number of Map, Set and array-end operations. Space is O(n). The whole design is one sentence: make removal O(1) by giving up an order nobody asked you to keep.

Median finder: two heaps that meet in the middle

addNum(x) adds a number to a stream and findMedian() returns the middle value of everything so far (the mean of the two middle values when the count is even). The obvious store is a sorted array. Finding where x belongs is a binary search, O(log n), but inserting there shifts the tail, so each addNum costs O(n). Re-sorting on every query is worse. One heap is no help either: it exposes the minimum or the maximum, and the median is neither.

Look at what the median needs. It does not need the data sorted, it needs the boundary between the smaller half and the larger half. Split the numbers into a lower half and an upper half. If the lower half sits in a max-heap, its top is the largest of the small numbers; if the upper half sits in a min-heap, its top is the smallest of the large ones. The two tops are exactly the middle elements. All that has to be maintained is two invariants: (1) every number in the lower half is at most every number in the upper half, and (2) the halves differ in size by at most one, with the extra element in the lower half.

addNum restores both in three steps and no branching on values. Push x into the lower half; then move that half's largest element across to the upper half, which guarantees invariant (1) whatever x was; then, if the upper half is now bigger, move its smallest back.

class Heap {
  constructor(before) {
    this.items = [];
    this.before = before; // before(a, b) is true when a belongs closer to the top than b
  }

  get size() {
    return this.items.length;
  }

  peek() {
    return this.items[0];
  }

  push(x) {
    const a = this.items;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (!this.before(a[i], a[parent])) break;
      [a[i], a[parent]] = [a[parent], a[i]];
      i = parent;
    }
  }

  pop() {
    const a = this.items;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        let best = i;
        const l = 2 * i + 1;
        const r = l + 1;
        if (l < a.length && this.before(a[l], a[best])) best = l;
        if (r < a.length && this.before(a[r], a[best])) best = r;
        if (best === i) break;
        [a[i], a[best]] = [a[best], a[i]];
        i = best;
      }
    }
    return top;
  }
}

class MedianFinder {
  constructor() {
    this.low = new Heap((a, b) => a > b); // max-heap: the smaller half
    this.high = new Heap((a, b) => a < b); // min-heap: the larger half
  }

  addNum(x) {
    this.low.push(x);
    this.high.push(this.low.pop()); // the biggest of the small half crosses over, so every low <= every high
    if (this.high.size > this.low.size) this.low.push(this.high.pop()); // low keeps the extra element
  }

  findMedian() {
    if (this.low.size === 0) return undefined;
    return this.low.size > this.high.size ? this.low.peek() : (this.low.peek() + this.high.peek()) / 2;
  }
}

Dry run: add 5, 2, 8, 1, 9

Row 2 shows the crossing: 2 is pushed into the lower half beside 5, 5 is the larger so it crosses to the upper half, and the sizes are already balanced. Row 4: pushing 1 into {2, 5} then moving the maximum 5 across leaves {1, 2} and {5, 8}, again balanced. Each row's median is the top of one heap, or the mean of two tops.

addNum costs O(log n) (a constant number of heap pushes and pops), findMedian is O(1), and space is O(n). The heap class is there because JavaScript has none; in an interview, state its interface (push, pop, peek, size) and offer to write it if the interviewer wants it.

Follow-ups the interviewer is waiting to ask

"All values are integers from 0 to 100." Then no heap is needed. Keep 101 counters, one per value, and a running total. The median is the k-th smallest for one or two ranks k, found by walking the counters from 0 upward until the running sum reaches k. That is at most 101 steps no matter how many numbers have arrived, so findMedian is O(1) and addNum is O(1). The extra shape to name is that a small value range replaces comparison-based structures with counting.

class BoundedMedian {
  constructor() {
    this.counts = new Array(101).fill(0); // counts[v] = how many times v (0..100) arrived
    this.total = 0;
  }

  addNum(x) {
    this.counts[x]++;
    this.total++;
  }

  _kth(k) {
    let seen = 0;
    for (let v = 0; v <= 100; v++) {
      seen += this.counts[v];
      if (seen >= k) return v; // the k-th smallest, 1-based
    }
  }

  findMedian() {
    if (this.total === 0) return undefined;
    const lowRank = Math.ceil(this.total / 2);
    const highRank = Math.floor(this.total / 2) + 1;
    return (this._kth(lowRank) + this._kth(highRank)) / 2;
  }
}

"99% of values are in 0 to 100, the rest are arbitrary." Keep the same 101 counters plus a count of values below 0 and a count above 100. At most 1% of the numbers lie on either side, far fewer than half, so the middle rank always falls inside 0 to 100; subtract the below-0 count when walking the ranks. "Slide a window: remove the oldest number." A heap cannot delete an arbitrary item cheaply, so either mark the item as deleted and discard it when it reaches a top (lazy deletion, keeping separate counts of live items per heap), or switch to an ordered structure.

Design HashMap: buckets, collisions and resizing

"Implement a hash map without using the built-in one." The interviewer is not after a clever structure; they want to see that you know what a hash map is. The idea in three steps. A hash function turns any key into a number. That number, taken modulo the length of an array, picks a bucket. Looking a key up is then one array access instead of a search.

The catch is unavoidable: there are far more possible keys than buckets, so two different keys will land in the same bucket. This is a collision, and it is normal, not a bug. The standard answer is separate chaining: each bucket is a short list of [key, value] pairs, and every operation is "find the bucket, then scan that short list". That scan is only short if the buckets stay nearly empty, so the map also tracks its load factor, the number of entries divided by the number of buckets, and doubles the array when it passes a threshold (here 0.75), re-distributing every pair.

function hashOf(key) {
  const text = String(key);
  let h = 0;
  for (let i = 0; i < text.length; i++) h = (Math.imul(h, 31) + text.charCodeAt(i)) | 0;
  return h >>> 0; // reinterpret as unsigned: a negative index would silently miss every bucket
}

class MyHashMap {
  constructor(capacity = 8) {
    this.buckets = Array.from({ length: capacity }, () => []); // each bucket: a short list of [key, value]
    this.size = 0;
  }

  _bucket(key) {
    return this.buckets[hashOf(key) % this.buckets.length];
  }

  put(key, value) {
    const bucket = this._bucket(key);
    for (const pair of bucket) {
      if (pair[0] === key) {
        pair[1] = value; // overwrite: size must not grow
        return;
      }
    }
    bucket.push([key, value]);
    this.size++;
    if (this.size > 0.75 * this.buckets.length) this._grow();
  }

  get(key) {
    for (const pair of this._bucket(key)) if (pair[0] === key) return pair[1];
    return -1;
  }

  remove(key) {
    const bucket = this._bucket(key);
    const i = bucket.findIndex((pair) => pair[0] === key);
    if (i === -1) return;
    bucket.splice(i, 1);
    this.size--;
  }

  _grow() {
    const old = this.buckets;
    this.buckets = Array.from({ length: old.length * 2 }, () => []);
    for (const bucket of old) {
      for (const pair of bucket) this._bucket(pair[0]).push(pair); // re-hash against the NEW length
    }
  }
}

Dry run: capacity 4, putting a, b, c, e, f (the hash of a single character is its character code)

The collision in row 4 disappeared after the resize only because 97 and 101 differ by 4, and 4 is a multiple of the old capacity but not the new one. That is the point of growing: more buckets spread the same keys out.

Costs, stated with their assumptions. With a hash function that spreads keys evenly and a bounded load factor, put, get and remove take expected O(1) time, because each bucket holds a constant number of pairs on average. A single resize is O(n), but doubling makes the total cost of n insertions O(n), so the amortized cost per put is O(1). If every key hashed to one bucket, all three operations would degrade to O(n); that is the worst case, and it is why the quality of the hash matters. Space is O(n + capacity).

The main alternative is open addressing: no lists, each entry lives directly in the array, and a collision probes the next slot. It uses less memory per entry and has better locality, but deletion becomes subtle: you cannot just empty a slot, because a later key may have probed past it to get where it is, so a removed entry must leave a marker (a tombstone) that lookups skip over and inserts may reuse. Naming that trap is usually enough; writing both versions is rarely asked.

Encode and decode strings: make the encoding say where each piece ends

Design encode(strs), which turns a list of strings into one string, and decode(text), which gives the list back. The strings can contain any character. Everything about the problem is in that last sentence.

The first idea is to join with a delimiter and split on it. It fails immediately, and it is worth showing why rather than asserting it. With "#" as the delimiter, ["a#b", "c"] decodes as ["a", "b", "c"]. Worse, [] and [""] both encode to the empty string, so decode has no way to tell them apart; in the naive version below, [""] comes back as [].

function encodeNaive(strs) {
  return strs.join("#");
}

function decodeNaive(text) {
  return text === "" ? [] : text.split("#");
}

Picking a rarer delimiter only moves the bug. Escaping works but is fiddly: once # is escaped, the escape character must be escaped too. The robust fix is a different idea: stop scanning for a boundary, and announce the length before the content. Write each string as its length, a separator, then exactly that many characters. The decoder reads the digits up to the first separator, then counts that many characters and does not look at what they are. A # or a digit inside the string cannot confuse it, because the decoder is never searching inside the string, only skipping it.

function encode(strs) {
  return strs.map((s) => s.length + "#" + s).join("");
}

function decode(text) {
  const out = [];
  let i = 0;
  while (i < text.length) {
    const hash = text.indexOf("#", i); // the first "#" after i ends the length: digits never contain one
    const length = Number(text.slice(i, hash));
    const start = hash + 1;
    out.push(text.slice(start, start + length)); // take exactly `length` characters, whatever they are
    i = start + length;
  }
  return out;
}

Dry run: decode of the text for ["lint", "c#de", "", "7#x"]

The encoded text is 4#lint4#c#de0#3#7#x.

Both functions are O(total length): each character is written once and examined once. The empty list encodes to "" and a list holding one empty string encodes to "0#", so those two inputs stay distinct. I round-tripped 3,000 random lists whose characters came from a deliberately hostile alphabet (#, digits, spaces, newlines, a NUL character, an accented letter, an emoji, a lone surrogate half, and the string "7#x") and every one decoded to what went in.

In real code you would reach for JSON.stringify and JSON.parse, which solve this problem with escaping. Say that first, then say why the interview version asks for something else: it is checking whether you can make an encoding unambiguous by construction. The same length-prefix idea is how many binary formats and network protocols frame their messages.

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 with lazy deletion or an 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
• "The value as of time t" with writes arriving in time order → a sorted list per key and a binary search for the last version not after t; if writes can arrive out of order, you pay for the insert
• "Return a random member" beside an O(1) delete → a dense array plus a map of positions, deleting by moving the last element into the hole
• "Most and least frequent key" where each count changes by exactly 1 → buckets of keys in a linked list sorted by count, spliced rather than searched
• "Implement X from scratch" or "make the encoding unambiguous" → name the collision or the ambiguity first, then remove it by construction: chaining plus a resize, or a length written before the content
• 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