Recalculate a Spreadsheet After a Cell Changes

Find every cell downstream of the change with a graph search, then topologically sort just that set with Kahn's algorithm, ignoring edges out of the changed cell. If the sort cannot place every affected cell, the leftovers contain a cycle: walk back through what each stuck cell reads to name the chain. Linear in the affected cells and their edges.

hardPattern: Graphs·From Devana's Microsoft question set

Problem

A spreadsheet cell can hold a formula that reads other cells. When one cell changes, everything that depends on it, directly or through other cells, has to be recomputed, and each cell has to be recomputed after every cell it reads. Recomputing the whole sheet on every keystroke is too slow.

Write recalculate(dependents, changed), where dependents maps a cell to the cells that read it. Return the cells to recompute, in a valid order. If the formulas contain a circular reference, raise an error that names the exact chain, such as A1 -> B1 -> A1, instead of looping forever.

def recalculate(dependents: dict[str, list[str]], changed: str) -> list[str]:
    """Cells to recompute in dependency order; raises CircularReference on a cycle."""

This is one of Devana's own questions, written in the style of Microsoft's interviews. It is not a question leaked from Microsoft, and Devana is not affiliated with Microsoft.

Constraints

• Return only the affected cells. The changed cell itself is not in the result.
• A cell reachable along two paths appears once, after all of its inputs that are being recomputed.
• When several cells are ready at the same time, the one that sorts first alphabetically goes first, so the order is deterministic.
• A cycle is reported starting from its alphabetically smallest cell.
• Up to 10^5 cells with formulas.

Examples

Input:  dependents = {"A1": ["B1", "C1"], "B1": ["C1"]}, changed = "A1"
Output: ["B1", "C1"]

Input:  dependents = {"A1": ["B1"], "B1": ["C1"], "C1": ["B1"]}, changed = "A1"
Output: CircularReference: B1 -> C1 -> B1

Hints

Open one at a time, and try the problem again after each.

Approach: from brute force to optimal

How to say it in the interview

Split the problem into two questions out loud: which cells change, and in what order. The first is reachability and the second is a topological sort, and the cycle report falls out of the second. Mention why edges out of the changed cell are not counted; it is the bug most candidates hit.

Solution

Python

import heapq

class CircularReference(Exception):
    pass

def recalculate(dependents, changed):
    # 1. Everything downstream of the change, and nothing else.
    affected, stack = set(), [changed]
    while stack:
        for d in dependents.get(stack.pop(), []):
            if d not in affected:
                affected.add(d)
                stack.append(d)

    # 2. Kahn's algorithm inside that set. The changed cell's value is
    #    already known, so edges out of it are not waited on.
    waiting = {cell: 0 for cell in affected}
    for cell in affected:
        for d in dependents.get(cell, []):
            if d in waiting:
                waiting[d] += 1
    ready = [cell for cell in affected if waiting[cell] == 0]
    heapq.heapify(ready)
    order = []
    while ready:
        cell = heapq.heappop(ready)
        order.append(cell)
        for d in dependents.get(cell, []):
            if d in waiting:
                waiting[d] -= 1
                if waiting[d] == 0:
                    heapq.heappush(ready, d)

    if len(order) < len(affected):
        stuck = affected - set(order)
        raise CircularReference(" -> ".join(find_cycle(dependents, stuck)))
    return order

def find_cycle(dependents, stuck):
    reads = {cell: [] for cell in stuck}        # cell -> stuck cells it reads
    for cell in stuck:
        for d in dependents.get(cell, []):
            if d in reads:
                reads[d].append(cell)
    # Every stuck cell reads another stuck cell, so walking back must repeat.
    path, seen_at = [], {}
    cell = min(stuck)
    while cell not in seen_at:
        seen_at[cell] = len(path)
        path.append(cell)
        cell = min(reads[cell])
    loop = path[seen_at[cell]:][::-1]           # reversed: now in formula order
    start = loop.index(min(loop))
    loop = loop[start:] + loop[:start]
    return loop + [loop[0]]

JavaScript

class CircularReference extends Error {}

function recalculate(dependents, changed) {
  const readers = (cell) => dependents[cell] ?? [];

  // 1. Everything downstream of the change, and nothing else.
  const affected = new Set();
  const stack = [changed];
  while (stack.length > 0) {
    for (const d of readers(stack.pop())) {
      if (!affected.has(d)) {
        affected.add(d);
        stack.push(d);
      }
    }
  }

  // 2. Kahn's algorithm inside that set; edges out of the changed cell are not waited on.
  const waiting = new Map([...affected].map((cell) => [cell, 0]));
  for (const cell of affected) {
    for (const d of readers(cell)) if (waiting.has(d)) waiting.set(d, waiting.get(d) + 1);
  }
  const ready = [...affected].filter((cell) => waiting.get(cell) === 0);
  const order = [];
  while (ready.length > 0) {
    ready.sort(); // alphabetical among the ready cells
    const cell = ready.shift();
    order.push(cell);
    for (const d of readers(cell)) {
      if (!waiting.has(d)) continue;
      waiting.set(d, waiting.get(d) - 1);
      if (waiting.get(d) === 0) ready.push(d);
    }
  }

  if (order.length < affected.size) {
    const placed = new Set(order);
    const stuck = [...affected].filter((cell) => !placed.has(cell));
    throw new CircularReference(findCycle(dependents, stuck).join(" -> "));
  }
  return order;
}

function findCycle(dependents, stuck) {
  const reads = new Map(stuck.map((cell) => [cell, []])); // cell -> stuck cells it reads
  for (const cell of stuck) {
    for (const d of dependents[cell] ?? []) if (reads.has(d)) reads.get(d).push(cell);
  }
  const min = (cells) => cells.reduce((a, b) => (b < a ? b : a));
  // Every stuck cell reads another stuck cell, so walking back must repeat.
  const path = [];
  const seenAt = new Map();
  let cell = min(stuck);
  while (!seenAt.has(cell)) {
    seenAt.set(cell, path.length);
    path.push(cell);
    cell = min(reads.get(cell));
  }
  const loop = path.slice(seenAt.get(cell)).reverse(); // now in formula order
  const start = loop.indexOf(min(loop));
  const rotated = [...loop.slice(start), ...loop.slice(0, start)];
  return [...rotated, rotated[0]];
}

Both versions are tested against the same cases, including every example on this page.

• The search in step 1 uses an explicit stack, so a long chain of formulas cannot overflow the call stack.
• Only edges inside the affected set are counted. Counting the changed cell's own edges would leave every direct dependent waiting forever and look like a cycle.
• JavaScript has no built-in heap, so the JavaScript version sorts the ready list instead. That is fine for small sheets; for large ones, use a binary heap as the Python version does.

Follow-up questions

Common mistakes

• Recomputing in the order the search discovered the cells, which can compute C1 before B1.
• Counting the changed cell's outgoing edges, which reports a cycle on every input.
• Detecting a cycle but reporting only "circular reference", with no chain.
• Recursing once per level of formulas, which overflows the call stack on long chains.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Related problems

• Degrees of Separation Between Members: Breadth-first search from both ends, expanding the smaller frontier, stopping at depth three.
• Build a Document Outline from Headings: Keep the open chain of headings on a stack and pop until the top is a shallower level.
• Graphs: the pattern guide, with more practice questions.