Design and simulation problems

The method: operations, targets, structures, invariants

A design question hands you a class and a list of method names. There is no clever algorithm hiding inside. What is graded is whether you can turn a paragraph of English into a small, correct machine: which data it keeps, what each method does to that data, and what stays true between calls. The design problems chapter covers the classic caches, counters and stores, and its opening teaches the habit of writing the operation table first. This chapter uses the same habit on a different family: iterators, games and simulations, versioned data, and small services with logs and feeds. Every problem here is solved the same way, in four steps.

The invariant step is the one candidates skip, and it is the one that turns a pile of fields into a design. An invariant is a sentence about the fields that is true when the constructor finishes and is true again when every method returns, whatever order the calls came in. Two such sentences appear again and again below: "these two structures describe the same set of things" (a queue and a set of the same cells) and "this counter equals what a full recount would give" (a running sum equal to the sum of the window). If you can say them out loud, you can also check them in code, and a section near the end does exactly that.

The table below shows steps 2 and 3 for most of the problems in this chapter. The naive column is not a deliberately weak baseline: it is what you would write first, and it is also what you will use later as a reference to test the fast version.

Iterators: hand out one value at a time

An iterator is an object that produces a sequence one value at a time and remembers where it is. The interview version asks for two methods: hasNext(), which says whether another value exists, and next(), which returns it and moves on. JavaScript's built-in protocol is the same idea with a different spelling: an object with a next() method that returns { value, done }, and an iterable is any object with a [Symbol.iterator]() method that returns one. for...of, spread and destructuring all consume that protocol.

The easy answer to "iterate over this structure" is to copy every value into an array in the constructor and walk the array. It is correct, and it usually loses the round, for two reasons. It spends O(N) memory and time before the first value is asked for, and it cannot work on a source that is huge or has no end. The better answer is lazy: keep only enough state to find the next value, and do the work when it is asked for. The design question then becomes: what is the smallest state that remembers my place?

Flatten a nested list with a stack of frames

The input is a list whose items are either integers or lists of the same kind, to any depth: [[1, 1], 2, [1, 1]]. The iterator must return 1, 1, 2, 1, 1. A place in this structure is a path: "third item of the outer list, second item of the list inside it". A path is exactly what a stack holds, so keep a stack with one frame per list you are currently inside. A frame is the list and the index of its next unread item.

Where should the work happen? Look at what each method must answer. hasNext() must be able to say "no" when the remaining items are all empty lists, as in [[], [[]]], so it cannot just check whether the top frame has items left. It has to dig down until it finds a real integer or runs out of frames. So let hasNext() do the digging and leave the stack pointing at the next integer; then next() only has to call it and read the value. This also makes hasNext() safe to call twice in a row, because the second call finds the stack already pointing at an integer and changes nothing.

class NestedIterator {
  constructor(nestedList) {
    this.stack = [{ list: nestedList, index: 0 }]; // one frame per list we are inside
  }

  hasNext() {
    while (this.stack.length > 0) {
      const top = this.stack[this.stack.length - 1];
      if (top.index === top.list.length) {
        this.stack.pop(); // this list is used up: go back to its parent
      } else if (Array.isArray(top.list[top.index])) {
        this.stack.push({ list: top.list[top.index], index: 0 }); // step into the inner list
        top.index++; // the parent resumes after it
      } else {
        return true; // the top frame points at a plain value
      }
    }
    return false;
  }

  next() {
    if (!this.hasNext()) throw new Error("no more values");
    const top = this.stack[this.stack.length - 1];
    return top.list[top.index++];
  }
}

Dry run: [[1, 1], 2, [1, 1]]

Each frame is written as index/length, outermost first.

The stack never holds more frames than the nesting depth, so memory is O(depth), and the nested list itself is not copied. Over a whole iteration each list is pushed once and popped once, and each integer is read once, so the total work is O(N + L) for N integers and L lists. One single hasNext() call can cost O(L) when it has to step over a long run of empty lists, which is why the honest bound is amortized.

The same idea as a generator

JavaScript can write the whole thing without a hand-made stack. A generator function (function*) returns an iterator whose body runs only when next() is called, and pauses at each yield. The language keeps the "where was I" state for you. Inside a generator, yield* hands control to another iterable until it is finished, which is exactly what flattening needs:

function* flattenLazy(list) {
  for (const item of list) {
    if (Array.isArray(item)) yield* flattenLazy(item); // hand over to the inner generator
    else yield item;
  }
}

[...flattenLazy([[1, 1], 2, [1, 1]])] gives [1, 1, 2, 1, 1]. Nothing is computed ahead: asking for two values runs the body only as far as the second yield, which is why the same shape works on a source that never ends. The price is a trade you should be able to name. The state lives in the call stack: in Node 24 we nested a list ten thousand levels deep and the generator stopped with a RangeError, while the explicit stack read the innermost value without trouble. Each value also passes through one generator per level of nesting on its way out, where the explicit stack reads it directly. A generator is also single-use: once it has been spread, a second spread gives an empty array. When an interviewer asks for hasNext() and next(), you can still use either version, and a small adapter turns the stack version into a real JavaScript iterable so that for...of works on it:

function asJsIterator(iterator) {
  return {
    [Symbol.iterator]() { return this; },
    next() {
      return iterator.hasNext() ? { value: iterator.next(), done: false } : { value: undefined, done: true };
    },
  };
}

Peeking iterator: one cached value

A peeking iterator wraps any iterator and adds peek(), which returns the next value without consuming it. The wrapped iterator only goes forward, so to look at a value and still deliver it later you must remember it. One slot is enough: the invariant is "if the slot is full it holds the next value the wrapper must return; if it is empty, the next value is still inside the wrapped iterator".

class PeekingIterator {
  constructor(iterator) {
    this.iterator = iterator;
    this.cached = null; // null, or a box { value } holding the peeked value
  }

  hasNext() {
    return this.cached !== null || this.iterator.hasNext();
  }

  peek() {
    if (this.cached === null) {
      if (!this.iterator.hasNext()) throw new Error("no more values");
      this.cached = { value: this.iterator.next() }; // pull once, remember it
    }
    return this.cached.value;
  }

  next() {
    if (this.cached !== null) {
      const { value } = this.cached;
      this.cached = null; // the lookahead slot is empty again
      return value;
    }
    return this.iterator.next();
  }
}

Dry run: wrapping an iterator over [4, 5, 6]

The pattern is one slot of lookahead. It is what a parser does when it looks at the next token before deciding what to do, and what a merge does when it compares the fronts of two inputs. If a problem needs to look several values ahead, the slot becomes a small queue.

Zigzag iterator: a queue of cursors

Given k lists of different lengths, return their values by taking one from each list in turn: for [1, 2, 3], [4, 5, 6, 7] and [8, 9] the order is 1, 4, 8, 2, 5, 9, 3, 6, 7. For two lists you can alternate with a flag. For k lists, whose turn it is and which lists are already finished both change as you go. The clean model is a queue of cursors. A cursor is a list and the index of its next value. Take the cursor at the front, read one value, and if it still has values, send it to the back of the line.

The queue is the first structure in this chapter that wants O(1) removal from the front, so here is a small one made of linked nodes, with a length and a peek. (The stacks and queues chapter builds a queue from two stacks instead, whose dequeue is O(1) amortized.) The Snake game and the bounded logger below use it too.

class Queue {
  constructor() {
    this.head = null; // the oldest node: dequeue takes from here
    this.tail = null; // the newest node: enqueue adds here
    this.length = 0;
  }

  enqueue(value) {
    const node = { value, next: null };
    if (this.tail === null) this.head = node;
    else this.tail.next = node;
    this.tail = node;
    this.length++;
  }

  dequeue() {
    if (this.head === null) throw new Error("the queue is empty");
    const { value } = this.head;
    this.head = this.head.next;
    if (this.head === null) this.tail = null; // it was the last node
    this.length--;
    return value;
  }

  peek() {
    return this.head === null ? undefined : this.head.value;
  }
}

class ZigzagIterator {
  constructor(lists) {
    this.queue = new Queue(); // the lists that still have values, in turn order
    for (const list of lists) {
      if (list.length > 0) this.queue.enqueue({ list, index: 0 });
    }
  }

  hasNext() {
    return this.queue.length > 0;
  }

  next() {
    if (!this.hasNext()) throw new Error("no more values");
    const cursor = this.queue.dequeue();
    const value = cursor.list[cursor.index++];
    if (cursor.index < cursor.list.length) this.queue.enqueue(cursor); // back of the line
    return value;
  }
}

Dry run: [1, 2, 3], [4, 5, 6, 7], [8, 9]

A cursor is written L1@0: the list that starts with 1, at index 0. The queue is shown front first.

Each call is O(1). The invariant is "the queue holds exactly the lists that still have values, in the order of their turns", and that is why finished lists need no special case: they are simply not put back. Memory is O(k). If the statement says the lists arrive as iterators instead of arrays, the cursor becomes a PeekingIterator, and the check "does this list have more?" becomes hasNext().

Tic-Tac-Toe: count the line, don't scan it

Design a game on an n by n board. move(row, col, player) places a mark for player 1 or player 2 and returns 0 if nobody has won, or the number of the player who just completed a full row, a full column or a full diagonal. The statement promises that every move is on an empty cell and that no move comes after a win.

The first version stores the board and, after each move, scans the row, the column and, when the cell is on one, the two diagonals. That is O(n) per move. It is right, and it repeats work: if the row already held two marks of this player and one more arrives, you walked all three cells just to learn what a count of 2 could have told you. The question to ask is what the win check needs to know about a line. Only whether all n of its cells belong to one player. So do not keep the cells; keep one number per line.

Give player 1 the value +1 and player 2 the value -1, and let every line (n rows, n columns and the two diagonals) hold the sum of the values of its marks. A line has n cells, so its sum can only reach +n if all n cells are player 1's, and only reach -n if all n are player 2's. Any mix pulls the total back toward zero. A move touches at most four counters: its row, its column, the main diagonal when row === col, and the anti-diagonal when row + col === n - 1. After updating them, check whether any of those counters has reached ±n.

class TicTacToe {
  constructor(n) {
    this.n = n;
    this.rows = new Array(n).fill(0); // +1 per cell of player 1, -1 per cell of player 2
    this.cols = new Array(n).fill(0);
    this.diagonal = 0; // cells with row === col
    this.antiDiagonal = 0; // cells with row + col === n - 1
  }

  move(row, col, player) {
    const delta = player === 1 ? 1 : -1;
    this.rows[row] += delta;
    this.cols[col] += delta;
    if (row === col) this.diagonal += delta;
    if (row + col === this.n - 1) this.antiDiagonal += delta; // the centre of an odd board hits both
    const complete = (total) => Math.abs(total) === this.n;
    if (complete(this.rows[row]) || complete(this.cols[col]) || complete(this.diagonal) || complete(this.antiDiagonal)) {
      return player;
    }
    return 0;
  }
}

Dry run: n = 3, player 1 takes the main diagonal

Read the second row: player 2's mark in row 0 cancels player 1's, so the row counter returns to 0, and a mixed line can never reach 3. The centre cell (1,1) added to both the diagonal and the anti-diagonal, because it lies on both. The last move pushes the diagonal to 3, and player 1 wins. Each move is O(1) and the memory is O(n), against the O(n²) of the board itself. This works because each cell is used at most once. If the statement allowed overwriting a cell or repeating a move, a counter would count the same cell twice, and you would have to keep the board or a Set of used cells.

Snake: a queue for order and a Set for lookup

new SnakeGame(width, height, food) starts a snake of length 1 at the top-left cell, (0, 0). food is a list of [row, col] pairs; only the first uneaten one is on the board, and the next appears when it is eaten. move(direction) takes "U", "D", "L" or "R" and returns the score, which is the number of foods eaten, or -1 if the game is over. The game ends when the head leaves the board or runs into the snake's body.

Write the operation table. Each move must do three things: add a new head, remove the old tail unless food was eaten, and check whether the new head hits the body. The body is a sequence with one end that grows and the other end that shrinks, which is a queue: the tail is the front, the head is the back. A queue is bad at one thing, though: "is this cell in the queue?" costs O(length) to answer. A hash set is the opposite. So keep both, and make the invariant explicit: the set holds exactly the cells of the queue. Every move changes both in the same breath.

Cells are stored as one number, row * width + col, so the set compares numbers rather than arrays (a Set of [row, col] arrays would never match, because two arrays with the same contents are different objects). The one subtle step is the collision test. When the snake does not eat, its tail moves forward in the same turn, so the cell the tail is leaving is free for the head. When the snake eats, the tail stays put and that cell is still taken. The code decides this before changing anything, so a move that ends the game leaves the structures untouched:

class SnakeGame {
  constructor(width, height, food) {
    this.width = width;
    this.height = height;
    this.food = food; // [row, col] pairs, served one at a time in this order
    this.eaten = 0;
    this.body = new Queue(); // cell keys, tail at the front and head at the back
    this.occupied = new Set(); // the same keys, for O(1) collision checks
    this.row = 0;
    this.col = 0;
    this.body.enqueue(0);
    this.occupied.add(0);
  }

  move(direction) {
    let row = this.row;
    let col = this.col;
    if (direction === "U") row--;
    else if (direction === "D") row++;
    else if (direction === "L") col--;
    else col++;
    if (row < 0 || row >= this.height || col < 0 || col >= this.width) return -1;

    const key = row * this.width + col; // one number per cell
    const next = this.food[this.eaten];
    const eating = next !== undefined && next[0] === row && next[1] === col;
    const tail = this.body.peek();
    if (this.occupied.has(key) && (eating || key !== tail)) return -1; // the tail cell is free if the tail moves

    if (eating) {
      this.eaten++; // grow: the tail stays where it is
    } else {
      this.body.dequeue();
      this.occupied.delete(tail);
    }
    this.body.enqueue(key);
    this.occupied.add(key);
    this.row = row;
    this.col = col;
    return this.eaten;
  }
}

Dry run: width 3, height 2, food [[1, 2], [0, 1]]

The body is written tail first, head last.

Each move is O(1) on average and the memory is O(length), at most width * height cells. The 2 by 2 board below shows the subtle case. With food at (0,1), (1,1) and (1,0), the moves R, D, L eat all three and the body becomes (0,0), (0,1), (1,1), (1,0), with the tail on (0,0). A fourth move, U, takes the head onto (0,0), the cell the tail is about to leave, and the game goes on with the score still 3. We ran the version that checks the body before removing the tail on the same four moves, and it returned 1, 2, 3, -1.

Snapshot Array: store changes, not copies

new SnapshotArray(length) holds length values, all starting at 0. set(index, value) changes one entry. snap() freezes the whole array and returns the snapshot's id, which is 0 for the first call, 1 for the second, and so on. get(index, snapId) returns what array[index] was when snapshot snapId was taken. The obvious way to freeze an array is to copy it, which costs O(length) time and memory per snap(): an array of 50,000 entries snapshotted 50,000 times would hold 2.5 billion numbers, nearly all of them copies of values that did not change.

What did change between snapshots? Only the entries that were set. So record changes, not states. For each index keep a list of [snapId, value] pairs, added in increasing order of snapshot id, because snapshots are taken in order. A set appends a pair tagged with the id of the snapshot that will capture it, the one not yet taken, which is the current counter. A second set to the same index before the next snap() overwrites that last pair, so each index stores at most one pair per snapshot.

get(index, snapId) then asks: of this index's pairs, which is the last one tagged snapId or lower? The tags are sorted, so that is a binary search for the first pair after snapId and a step back by one. If that first-after position is 0, the index had not been set by then, and the answer is the initial 0. This is the same versioned lookup as the time-based store in the design problems chapter, with snapshot ids standing in for timestamps; the search loop is the "first index with a value greater than the target" form from the binary search chapter.

class SnapshotArray {
  constructor(length) {
    this.history = Array.from({ length }, () => []); // per index: [snapId, value] pairs, snapIds ascending
    this.snapId = 0; // the id the NEXT snapshot will get
  }

  set(index, value) {
    const versions = this.history[index];
    const last = versions[versions.length - 1];
    if (last !== undefined && last[0] === this.snapId) last[1] = value; // same snapshot: overwrite
    else versions.push([this.snapId, value]);
  }

  snap() {
    return this.snapId++; // returns the id that was just taken, then moves on
  }

  get(index, snapId) {
    const versions = this.history[index];
    let lo = 0;
    let hi = versions.length;
    while (lo < hi) { // find the first version taken after snapId
      const mid = (lo + hi) >> 1;
      if (versions[mid][0] > snapId) hi = mid;
      else lo = mid + 1;
    }
    return lo === 0 ? 0 : versions[lo - 1][1]; // the version just before it; 0 if there is none
  }
}

Dry run: history of index 0

The search itself, on [[0, 10], [2, 20], [5, 30], [9, 40]] for get(..., 6):

set and snap are O(1), get is O(log v) where v is the number of recorded changes at that index, and the memory is O(length + total sets). The constructor allocates one empty list per index; if the length is huge and few indices are ever set, a Map from index to list allocates only for the indices touched.

Browser history: an array with a pointer, or two stacks

new BrowserHistory(homepage) starts on one page. visit(url) goes to a new page and erases every page that was ahead of the current one. back(steps) and forward(steps) move that many pages, stopping at the ends of the history, and return the page they land on. This question is a good warm-up for the method, because both standard answers are right and the conversation is about which one you would choose.

One array and a pointer. The history is a line of pages and one of them is on screen. Keep the pages in an array and the index of the current page. back and forward only move the index, and clamp it to the range 0 to length - 1. visit cuts the array to current + 1 entries, pushes the new page and moves the pointer onto it. Setting pages.length to a smaller number removes the entries past it.

Two stacks. Keep the pages behind you on one stack, the pages ahead on another, and the current page in a variable. Going back moves the current page onto the forward stack and pops one from the back stack, and going forward does the reverse. A visit pushes the current page onto the back stack, makes the new page current and empties the forward stack.

class BrowserHistory {
  constructor(homepage) {
    this.pages = [homepage];
    this.current = 0; // index of the page on screen
  }

  visit(url) {
    this.pages.length = this.current + 1; // forget every page ahead of us
    this.pages.push(url);
    this.current++;
  }

  back(steps) {
    this.current = Math.max(0, this.current - steps);
    return this.pages[this.current];
  }

  forward(steps) {
    this.current = Math.min(this.pages.length - 1, this.current + steps);
    return this.pages[this.current];
  }
}

class BrowserHistoryStacks {
  constructor(homepage) {
    this.backStack = []; // pages behind us, the nearest on top
    this.forwardStack = []; // pages ahead of us, the nearest on top
    this.page = homepage;
  }

  visit(url) {
    this.backStack.push(this.page);
    this.page = url;
    this.forwardStack = []; // a new visit erases the forward pages
  }

  back(steps) {
    while (steps > 0 && this.backStack.length > 0) {
      this.forwardStack.push(this.page);
      this.page = this.backStack.pop();
      steps--;
    }
    return this.page;
  }

  forward(steps) {
    while (steps > 0 && this.forwardStack.length > 0) {
      this.backStack.push(this.page);
      this.page = this.forwardStack.pop();
      steps--;
    }
    return this.page;
  }
}

Dry run: homepage "a", then visit b, visit c, back 1, visit d, forward 2, back 5

The two-stack form is the same machine as undo and redo: the back stack is the undo stack, the forward stack is redo, and doing a new action clears redo. The next section applies that picture to a text editor.

Text editor: two stacks around the cursor

A text editor with a cursor supports addText(text), which inserts at the cursor and leaves the cursor after the new text; deleteText(k), which deletes up to k characters to the left of the cursor and returns how many it deleted; cursorLeft(k) and cursorRight(k), which move the cursor by up to k places, and return the last (up to) 10 characters to the left of the cursor. A single string with an index looks natural, but a string cannot be changed in place: every insertion or deletion builds a new string, and in the usual cost model that work grows with the length of the text. With long text and many operations that is the cost the question is probing.

Everything an editor does happens at the cursor. So split the text there: keep the characters before the cursor on one stack, and the characters after it on another, each with the character nearest the cursor on top. Typing pushes onto the left stack. Deleting pops it. Moving the cursor left pops a character from the left stack and pushes it onto the right stack, because that character is now after the cursor, and moving right is the reverse. The full text is the left stack, then the right stack read from top to bottom.

class TextEditor {
  constructor() {
    this.left = []; // characters before the cursor, the nearest on top
    this.right = []; // characters after the cursor, the nearest on top (so the text is reversed)
  }

  addText(text) {
    for (const ch of text) this.left.push(ch);
  }

  deleteText(k) {
    let removed = 0;
    while (removed < k && this.left.length > 0) {
      this.left.pop();
      removed++;
    }
    return removed;
  }

  cursorLeft(k) {
    while (k > 0 && this.left.length > 0) {
      this.right.push(this.left.pop()); // one character crosses the cursor
      k--;
    }
    return this.#beforeCursor();
  }

  cursorRight(k) {
    while (k > 0 && this.right.length > 0) {
      this.left.push(this.right.pop());
      k--;
    }
    return this.#beforeCursor();
  }

  #beforeCursor() {
    return this.left.slice(-10).join(""); // at most the 10 characters just before the cursor
  }
}

Dry run: the cursor is shown as | between the two halves

addText costs O(length of the text), deleteText(k) and the two cursor moves cost O(k), and the returned string costs at most O(10). No operation depends on the total length of the document: an edit costs the size of the edit, and the only other cost is the distance the cursor travels in a move. A gap buffer is the same machine in one array: the text before the cursor sits at the start, the text after it sits at the end, and the unused space, the gap, sits between them at the cursor. Moving the cursor shifts characters across the gap, exactly like moving them between the two stacks, and typing fills the gap from the left. Say that in the interview as an option; the two-stack form is shorter to write and has the same costs.

News feed: merge k sorted streams with a heap

Design a small social feed. postTweet(userId, tweetId) adds a post. follow(a, b) and unfollow(a, b) change who a user reads. getNewsFeed(userId) returns the ids of the ten most recent posts among the user's own and those of everyone they follow, newest first. Do the operation table: posting, following and unfollowing are each one change to a map or a list, so O(1) on average. The one hard operation is the feed.

The naive feed collects every post of every followed user, sorts the lot by time, and takes ten. It costs O(P log P) for P posts in total, and it sorts thousands of posts to return ten. Look at what you already have. Each user's posts were appended in the order they were made, so each user's list is already sorted by time. The feed is a merge of several sorted lists, and you only need the first ten items of the merged result. That is the k-way merge from the heaps chapter, run from the newest end.

Put the newest post of each source in a max-heap by time. The top of the heap is the newest post anywhere. Pop it, add it to the feed, and push the next-newest post from the same user. Stop after ten posts or when the heap is empty. Each heap entry is a small cursor, a list and an index, so nothing is copied. The code below uses the comparator-based Heap class from the heaps chapter (new Heap(compare, items), push, pop, size); give it the heap's order as the comparator and it does the rest.

One decision is easy to get wrong: what to order by. Tweet ids are labels and need not rise with time, and a real clock can repeat a value for two posts. Keep a counter inside the object, increase it on every post, and store its value with the post. Then "newer" is a plain number comparison with no ties.

class NewsFeed {
  constructor() {
    this.clock = 0; // a global counter: it never repeats, unlike a timestamp
    this.posts = new Map(); // userId -> posts, oldest first
    this.following = new Map(); // userId -> Set of followed userIds
  }

  postTweet(userId, tweetId) {
    if (!this.posts.has(userId)) this.posts.set(userId, []);
    this.posts.get(userId).push({ time: this.clock++, id: tweetId });
  }

  follow(followerId, followeeId) {
    if (!this.following.has(followerId)) this.following.set(followerId, new Set());
    this.following.get(followerId).add(followeeId);
  }

  unfollow(followerId, followeeId) {
    this.following.get(followerId)?.delete(followeeId);
  }

  getNewsFeed(userId, limit = 10) {
    const sources = new Set(this.following.get(userId) ?? []);
    sources.add(userId); // you always see your own posts

    const newest = [];
    for (const source of sources) {
      const list = this.posts.get(source);
      if (list !== undefined) newest.push({ list, index: list.length - 1 }); // each stream starts at its newest post
    }
    const heap = new Heap((a, b) => b.list[b.index].time - a.list[a.index].time, newest); // newest time first

    const feed = [];
    while (feed.length < limit && heap.size() > 0) {
      const top = heap.pop();
      feed.push(top.list[top.index].id);
      if (top.index > 0) heap.push({ list: top.list, index: top.index - 1 }); // that stream's next-newest post
    }
    return feed;
  }
}

Dry run: the feed of user 1, who follows users 2 and 3

Posts, in the order they were made: user 1 posts 11 (time 0), user 2 posts 21 (time 1), user 1 posts 12 (time 2), user 3 posts 31 (time 3), user 2 posts 22 (time 4). The feed has limit 4. A heap entry is written user@time.

The feed is [22, 31, 12, 21]. User 1's first post, 11, was never touched, and neither were any older posts: the heap did only as much work as the answers needed. With f sources (the followed users plus the user), building the starting list and heapifying it costs O(f), and each of the K results is one pop and at most one push, O(log f) each. That is O(f + K log f) per feed, against O(P log P) for the naive sort, where P can be far larger than K. After unfollow(1, 2) the same call returns [31, 12, 11], because user 2 is no longer a source.

This merges at read time: the cost is paid when someone asks for a feed. The alternative that a large system might choose is to copy each new post into every follower's own list when it is written, so a read is a lookup and a write is expensive. Name both and say which operation you are optimizing; for the question as asked, the heap merge is the expected answer.

Logs and counters: logger, moving average, underground

Three short problems share one skill: keep just enough about the past to answer the next call. The design problems chapter already has the hit counter and the sliding-window rate limiter. These three are smaller, and each hides a different trap.

Logger rate limiter: print a message at most once per window

shouldPrint(timestamp, message) returns true if the message may be printed now, and false if the same message was printed less than 10 seconds ago. Timestamps arrive in non-decreasing order. The simplest honest structure is a map from message to the first timestamp at which it may print again. A call that prints sets that to timestamp + 10; a call that is refused changes nothing.

class Logger {
  constructor(window = 10) {
    this.window = window;
    this.nextAllowed = new Map(); // message -> the first timestamp it may print again
  }

  shouldPrint(timestamp, message) {
    const allowed = this.nextAllowed.get(message);
    if (allowed !== undefined && timestamp < allowed) return false; // a refusal changes nothing
    this.nextAllowed.set(message, timestamp + this.window);
    return true;
  }
}

Each call is O(1) on average. The trap is the refusal: if a refused call also stored timestamp + 10, the refusal at time 3 would have moved x's deadline to 13, and the call at time 11 would have been refused too. That is a different rule (a message must be quiet for 10 seconds before it prints again), so ask which one is meant. The second trap is memory. The map keeps every message ever seen, forever. If the messages are unbounded, keep only the ones that are still blocked: a queue of (time, message) in print order, and a set of the blocked messages. Before each call, remove from the front of the queue every entry whose block has ended.

class BoundedLogger {
  constructor(window = 10) {
    this.window = window;
    this.printed = new Queue(); // { time, message } in the order printed
    this.recent = new Set(); // the messages that are still blocked
  }

  shouldPrint(timestamp, message) {
    while (this.printed.length > 0 && this.printed.peek().time + this.window <= timestamp) {
      this.recent.delete(this.printed.dequeue().message); // its block has ended: forget it
    }
    if (this.recent.has(message)) return false;
    this.recent.add(message);
    this.printed.enqueue({ time: timestamp, message });
    return true;
  }
}

At time 11 the entry for x printed at time 1 has ended (1 + 10 is not more than 11), so it leaves the set and x prints; at time 100 everything has expired and the set holds one message. Each entry is added once and removed once, so a call is O(1) amortized, and the memory is the number of messages printed within the last window. This version needs the timestamps to be non-decreasing, because it expires from the front of the queue.

Moving average with a ring buffer

next(value) receives the next number of a stream and returns the average of the last size numbers (or of all of them, until there are that many). Averaging the window on every call costs O(size). Keep the sum instead: when a value arrives, add it, and subtract the value that falls out. You need to know which value falls out, and it is the oldest one, so store the window in a fixed array used as a ring: the slot for the n-th value is n % size, which is where the oldest value sits. The ring starts filled with zeros, so subtracting what is in a slot that was never written subtracts nothing.

class MovingAverage {
  constructor(size) {
    this.window = new Array(size).fill(0); // a ring: the oldest value is overwritten first
    this.count = 0; // how many values have arrived in total
    this.sum = 0; // the sum of what is in the ring
  }

  next(value) {
    const slot = this.count % this.window.length;
    this.sum += value - this.window[slot]; // add the newcomer, drop the value it replaces
    this.window[slot] = value;
    this.count++;
    return this.sum / Math.min(this.count, this.window.length);
  }
}

Each call is O(1) and the memory is O(size). The invariant is " sum equals the sum of the numbers in the ring". It holds exactly for integers whose running sum stays below 2⁵³. For fractions it can drift. We ran this class with size 3 on 0.1, 0.2, 0.3, 0.4: the last call returned 0.30000000000000004, while averaging the window 0.2, 0.3, 0.4 directly gave 0.3. A large value that leaves the window can do worse: with size 2 and the stream 1e16, 1, 2, the third call returned 1, though the window 1, 2 averages 1.5, because adding 1 to 1e16 changes nothing and the 1 was lost. If exactness matters for fractions, recompute the window sum or compare with a tolerance.

Underground system: store the sum and the count, not the average

checkIn(id, station, time) and checkOut(id, station, time) record a card's trip; getAverageTime(from, to) returns the average duration over every completed trip that started at from and ended at to. A card has at most one open trip at a time. Two structures are needed and each answers one question. The open trips, a map from card id to where and when it checked in, answer "where did this card start?". The route totals answer "what is the average?", and the answer there is not to store the average: an average of averages is wrong, and an average alone cannot be updated without knowing how many trips it covers. Store the sum of durations and the number of trips per route, add to both on every check-out, and divide only when asked.

class UndergroundSystem {
  constructor() {
    this.checkedIn = new Map(); // card id -> { station, time } of the open trip
    this.trips = new Map(); // route key -> { sum, count }
  }

  checkIn(id, station, time) {
    this.checkedIn.set(id, { station, time });
  }

  checkOut(id, station, time) {
    const { station: from, time: start } = this.checkedIn.get(id);
    this.checkedIn.delete(id);
    const key = JSON.stringify([from, station]); // a route is an ordered pair
    const total = this.trips.get(key) ?? { sum: 0, count: 0 };
    total.sum += time - start;
    total.count++;
    this.trips.set(key, total);
  }

  getAverageTime(startStation, endStation) {
    const total = this.trips.get(JSON.stringify([startStation, endStation]));
    return total.sum / total.count; // divide only when asked
  }
}

Every operation is O(1) on average, and the memory is the number of open trips plus the number of distinct routes. The route key deserves care. The tempting key is the two names joined with a comma, and it breaks when a name contains the separator: ("a,b", "c") and ("a", "b,c") both become "a,b,c". Serializing the pair with JSON.stringify keeps them apart, and a nested Map would too. An array used directly as a Map key does not work either, since two arrays with equal contents are two different keys. Also remember that a route is directional: Park to Mill and Mill to Park are different keys.

Simulating by events: a parking lot

Some design questions describe a small world that changes by events: a car arrives, a car leaves. The method does not change. List the events, say what each does to the state, and make the state small enough that every event leaves it consistent. A parking lot with numbered slots is a short example: park() gives the arriving car the lowest-numbered free slot and a ticket, or reports that the lot is full, and leave(ticket) frees the slot that ticket holds.

"Lowest free slot" needs a structure that finds the minimum, and the slots keep coming back in any order, so a min-heap of free slot numbers fits: park pops it, leave pushes the slot back. A map from ticket to slot says where each car is. The invariant is that every slot is in exactly one of the two places, so parked.size + free.size() === capacity after every event.

class ParkingLot {
  constructor(slots) {
    this.capacity = slots;
    this.free = new Heap((a, b) => a - b, Array.from({ length: slots }, (_, i) => i + 1)); // free slot numbers, lowest first
    this.parked = new Map(); // ticket -> slot
    this.nextTicket = 1;
  }

  park() {
    if (this.free.size() === 0) return null;
    const slot = this.free.pop();
    const ticket = this.nextTicket++;
    this.parked.set(ticket, slot);
    return { ticket, slot };
  }

  leave(ticket) {
    const slot = this.parked.get(ticket);
    if (slot === undefined) return false;
    this.parked.delete(ticket);
    this.free.push(slot); // the slot is free again
    return true;
  }
}

Park and leave are O(log s) for s slots. The line that protects the invariant is the check on the ticket: if leave pushed a slot without checking that the ticket was still open, the same slot could sit in the heap twice and be given to two cars. If events carry times and must be processed in time order, the same heap idea, ordered by time instead of by slot number, drives the whole simulation: pop the earliest event, apply it, push the events it causes.

Check your design against a naive twin

A design class has no single output to eyeball, so test it the way you derived it. For every class here, write the naive version too: the one that stores everything and rescans, rebuilds or recounts. It is too slow to submit and easy to get right. Then drive both with the same random sequence of calls, compare every return value, and after every call check the invariant you stated. A mismatch tells you the exact call that broke the class, and a violated invariant tells you which sentence stopped being true.

function seededRandom(seed) {
  let state = seed;
  return (n) => {
    state = (state * 16807) % 2147483647; // a small deterministic generator: the same seed replays the same run
    return state % n;
  };
}

function compareToTwin({ makePair, randomCall, invariant, runs, steps }) {
  let calls = 0;
  for (let run = 1; run <= runs; run++) {
    const random = seededRandom(run);
    const { fast, naive } = makePair(random);
    for (let step = 0; step < steps; step++) {
      const { method, args } = randomCall(random);
      const got = fast[method](...args);
      const want = naive[method](...args);
      if (JSON.stringify(got) !== JSON.stringify(want)) {
        throw new Error("run " + run + ", step " + step + ": " + method + "(" + args + ") gave " + JSON.stringify(got) + ", the twin says " + JSON.stringify(want));
      }
      if (invariant) invariant(fast);
      calls++;
    }
  }
  return calls;
}

The harness takes a function that makes the fast class and its twin, a function that picks a random call, and an invariant. Here it checks the array-and-pointer history against a twin that rebuilds the list on every visit:

class NaiveBrowserHistory {
  constructor(homepage) {
    this.pages = [homepage];
    this.current = 0;
  }

  visit(url) {
    this.pages = [...this.pages.slice(0, this.current + 1), url]; // rebuild the whole list: slow and obviously right
    this.current = this.pages.length - 1;
  }

  back(steps) {
    for (let i = 0; i < steps; i++) if (this.current > 0) this.current--;
    return this.pages[this.current];
  }

  forward(steps) {
    for (let i = 0; i < steps; i++) if (this.current < this.pages.length - 1) this.current++;
    return this.pages[this.current];
  }
}

const calls = compareToTwin({
  runs: 500,
  steps: 60,
  makePair: () => ({ fast: new BrowserHistory("home"), naive: new NaiveBrowserHistory("home") }),
  randomCall: (random) => {
    const choice = random(3);
    if (choice === 0) return { method: "visit", args: ["page" + random(100)] };
    return { method: choice === 1 ? "back" : "forward", args: [random(4)] };
  },
  invariant: (history) => {
    if (history.current < 0 || history.current >= history.pages.length) throw new Error("the pointer left the history");
  },
});

That run makes 30,000 calls and compares every return value. To see that the harness can fail, we broke the class two ways. Changing the lower clamp of back from 0 to 1 failed at run 1, step 0, with back(1) returning undefined where the twin said "home". Cutting pages.length to current instead of current + 1 was caught by the invariant. The classes in this chapter were each checked this way before their code was copied here. Which invariant to assert depends on the class:

In an interview you will not run a harness, but the habit transfers. After writing the class, walk one short sequence by hand and say the invariant after each call, and name the edge cases you would test: an empty input, one element, a repeated call, a call at the boundary, a call after the end.

Recognizing it in an unseen problem

• The prompt is a class with named methods and no input array to process, and the costs per method are stated or implied. Write the operation table before any code.
• "Implement an iterator", hasNext, next, peek: a one-value lookahead slot, a stack of frames for nesting, or a queue of cursors for interleaving. Do the work in hasNext when it has to find the next real value.
• A game board with a win or collision check each turn: do not rescan the board. Ask what the check really needs, then keep a counter per line, or a set beside the ordered body.
• A sequence with one growing end and one shrinking end, plus a membership question: a queue and a set, kept in step.
• "As of snapshot or version t": record changes with their version tag, and binary search for the last tag at or before t.
• Undo, redo, back, forward, cursor: two stacks around a middle point, or an array and a pointer when jumps are allowed.
• "The k most recent across several sources": each source is already sorted, so a heap of cursors merges them and stops after k.
• "Average, count or rate over a window or a group": store sums and counts instead of averages; for a sliding window, a ring buffer and a running sum.
• "Lowest-numbered free", "next to expire", "earliest event": a heap, together with a map that says what each entry is.
• Pitfalls: doing the digging in next only, a falsy value taken for "empty", a key built by joining strings, a refusal that changes state, a pointer that leaves the array, a heap entry pushed twice, and a second structure that falls out of step with the first.