How do spreadsheet and dependency engines work, step by step?

In this article

1. Before you start
2. Why interviewers ask this
3. Spreadsheet and dependency engines from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the industry coding rounds guide, where applied, practical problems are collected.

Why interviewers ask this

Interviewers use this problem because it looks like a toy and hides a real design. A candidate who evaluates formulas in row order, or recomputes the whole sheet after every edit, produces something that works on the demo and fails on the first forward reference. Candidates report it in interviews at AI labs and large tech companies, sometimes as a practical alternative to a puzzle-style round, with wording that asks for formulas that refer to other cells and for edits that reach every dependent cell.

A weak answer evaluates by recursion with no memory and no cycle check. A strong answer separates three jobs: record who depends on whom, order the evaluation, and decide what to redo after an edit. A Staff-level answer adds the questions around them: what to do with a cycle, and whether a recomputed but unchanged value should keep spreading. Applied design problems such as the in-memory database assessment and wider low level design questions test the same habit of modelling state before coding.

Spreadsheet and dependency engines from first principles

Dirty cell

A dirty cell is a cell marked as needing recalculation because its own input, or an input of one of its precedents, changed; Excel marks every cell that depends on new data this way (Microsoft Learn, as of October 2026).

Cutoff

A cutoff is a rule that stops propagation when a recomputed cell holds the same value as before, so its dependents are not recomputed.

In plain words

Think of a recipe card box. Each card says "take the number on card 3, add one." You never reread every card after changing card 3. You flip only to the cards that mention card 3. Then you flip to the cards that mention those. The analogy breaks in one place: real cards can point at each other in a loop. Then the recipe has no first step.

In one precise sentence, the engine keeps a directed graph of references, evaluates cells in an order where precedents come first, and after an edit re-evaluates only the cells reachable from the edited cell.

Excel describes its own work, per the Microsoft Learn recalculation page, as three stages: building a dependency tree, building a calculation chain, and recalculating cells. The page says "tree", but mathematically the structure is a directed graph, and a directed acyclic graph (DAG) when no cycles exist.

Step 1: A formula's references become edges

Parsing a formula yields the cells it reads. The engine stores them twice: a precedents map from each cell to the cells it reads, and a dependents map that is the reverse. The precedents map answers "what do I need to compute this?" and the dependents map answers "who is affected if this changes?"

Input: the text of every formula. Output: two hash maps. In the worked sheet below, B1 holds A1+1, so B1 has the precedent A1 and A1 has the dependent B1. Python's graphlib uses the precedents direction, mapping each node to its predecessors, so the spreadsheet's dependents map is the reverse of that convention. You now have the graph; the next step turns it into an evaluation order.

Step 2: A topological order puts every precedent first

Evaluation order comes from the graph, never from row or column position. Kahn's algorithm builds it: count each cell's unevaluated precedents, put the cells with zero in a queue, emit one, and subtract one from the count of each of its dependents; any dependent that reaches zero joins the queue.

Input: the precedents map. Output: a list in which every cell follows the cells it reads. A forward reference, such as A1 reading Z9, is fine, because Z9 simply comes first. Each cell is emitted once and each reference is examined once, so the work grows with the number of cells plus the number of references. Excel keeps this order as a calculation chain, a list of all formula cells in the order they should be calculated (Microsoft Learn, as of October 2026). It also adapts the chain: if a formula reads a cell that has not been calculated yet, Excel moves the formula's own cell and its dependents down the chain and carries on, as the same page describes.

Step 3: A cycle leaves some cells never ready

A circular reference is a loop of references in which each cell, directly or through others, reads itself. Kahn's algorithm exposes it for free: cells in a loop each wait for another cell in the loop, so their counts never reach zero and they never enter the queue. If the output is shorter than the number of cells, a cycle exists.

Input: the same counts. Output: the cells left over. Those leftovers include cells that merely sit downstream of the loop, so they are not the loop itself. To report the loop, run a depth-first search that follows the precedents map and keep the current path; reaching a cell already on the path closes the cycle. Python's graphlib reports cycles too: it raises CycleError when it detects one, and the cycle is available as a list of nodes.

Step 4: An edit marks the reachable cells dirty

An edit changes one cell and invalidates everything that reads it, directly or through others. The engine walks the dependents map from the edited cell, depth-first or breadth-first, and marks every cell it reaches as dirty. It does not evaluate anything during this walk.

Input: the edited cell and the dependents map. Output: the dirty set. Excel does the same marking: when new data or formulas are entered, it marks every cell that depends on them as needing recalculation (Microsoft Learn, as of October 2026). Cells that are not reachable stay clean and keep their stored values. This is why the common belief that a spreadsheet recomputes everything on every edit is wrong. The exceptions are volatile functions, which recalculate every time, and a full calculation, which recalculates everything. A full structural change, such as entering a new formula, rebuilds the graph and the chain instead.

Step 5: Dirty cells are recomputed in order, optionally with a cutoff

Recalculation visits the dirty cells in topological order and evaluates each formula against the already-final values of its precedents. Because precedents come first, no cell reads a stale value, and each dirty cell is evaluated once.

Input: the dirty set and the order. Output: updated values. A cutoff adds one rule: if a cell's new value equals its old value, its dependents are not marked from it. Excel has no cutoff: its performance documentation says it keeps calculating cells that depend on previously calculated cells even when the previous cell's value did not change, and Mokhov, Mitchell and Peyton Jones (2018) record the same in their classification of build systems. A candidate who adds a cutoff goes beyond what the Excel documentation describes.

1 · References2 · Order3 · Cycle check4 · Mark dirty5 · RecomputeReplay

Step-by-step description

1. Formula references become graph edges.
2. A topological order puts precedents first.
3. Cells that never become ready mean a cycle.
4. An edit marks reachable cells dirty.
5. Dirty cells are recomputed in order.

• Formula references become edges of a dependency graph.
• A topological order puts every precedent first.
• Only dirty cells are recomputed, in order.

Worked example

Take a sheet with two constants and six formulas (illustrative): A1 is 5, E1 is 7, B1 is A1+1, C1 is B1*A1, D1 is B1+C1, F1 is E1+1, G1 is max(A1,100) and H1 is G1+1. The sheet has 8 reference edges, and one valid topological order is A1, E1, B1, G1, F1, C1, H1, D1.¹ Initial values are 6 for B1, 30 for C1, 36 for D1, 8 for F1, 100 for G1 and 101 for H1.¹

Now edit A1 from 5 to 6. The dependents map gives A1 the dependents B1, C1 and G1, and walking onward adds D1 and H1, so the dirty set is B1, C1, D1, G1 and H1; F1 is untouched.¹ Recomputing in order gives B1 as 7, C1 as 42 and D1 as 49, while G1 is still 100 because max(6,100) is 100, and so H1 is still 101.¹

The cutoff saves one evaluation because G1 came out unchanged, so H1 was never queued.¹ On a sheet of thousands of cells the gap is far larger, because the untouched part of the sheet is skipped completely.

Text description of the diagram

• Recomputing every formula cell takes 6 evaluations.
• Recomputing dirty cells only takes 5 evaluations.
• Dirty cells with a cutoff take 4 evaluations.

Now the cycle case: let A1 read B1, B1 read A1, and C1 read B1. No cell has zero precedents, so the order is empty and all three cells are left over; the depth-first path that closes the loop is A1, B1, A1, and C1 is only downstream of it.¹

Trade-offs and edge cases

The three strategies differ in bookkeeping, not in answers. Recompute-all keeps no extra state and is correct, which suits a tiny sheet. Dirty-only needs the dependents map and a dirty set. A cutoff also needs the old value of each cell to compare against.

Text description of the diagram

• Recompute-all keeps no extra state.
• Dirty-only keeps a dependents map and a dirty set.
• A cutoff also keeps the old value of each cell.

Edge cases a Staff reader expects:

• Volatile functions. A volatile function is a function that is recalculated at every recalculation even when no precedent changed, and per Microsoft Learn, as of October 2026 it always recalculates. Decision Models notes that direct dependents of a volatile function always recalculate: with =now() in A1, A2 reading A1 and A3 reading A2, all three recalculate each time. In an engine, treat a volatile cell as a dirty root at every recalculation and mark its dependents from it.
• Dynamic dependencies. If a formula's precedents are computed at run time, the graph cannot be fixed in advance; Mokhov and colleagues class Excel as having dynamic dependencies, handled by moving cells down the chain and restarting.
• Manual mode. Marking dirty and evaluating are separate steps, so an engine can mark at edit time and evaluate later; per Microsoft Learn, recalculation follows marking immediately in automatic mode and happens later otherwise.
• Cycle policy. Rejecting the edit is the simplest policy. A second policy iterates the cycle to a fixed point under an iteration cap: evaluate the cells of the loop repeatedly until values move less than a tolerance or the cap is reached.

The same ordering idea resolves library installs and component load order, which candidates report as dependency-resolution questions; the last follow-up below works one through.

How to answer it in an interview

The spoken structure: name the graph, give the order, handle the cycle, then explain the dirty set and the cutoff. Here is the order step in short Python; the explanation is in Step 2. Every cell, constants included, must be a key of deps, with an empty list for a constant.

from collections import deque

def recalc_order(deps):
    """deps maps each cell to the cells its formula reads."""
    waiting = {c: len(d) for c, d in deps.items()}
    users = {c: [] for c in deps}
    for c, d in deps.items():
        for p in d:
            users[p].append(c)
    ready = deque(c for c, n in waiting.items() if n == 0)
    order = []
    while ready:
        c = ready.popleft()
        order.append(c)
        for u in users[c]:
            waiting[u] -= 1
            if waiting[u] == 0:
                ready.append(u)
    if len(order) != len(deps):
        done = set(order)
        stuck = [c for c in deps if c not in done]
        raise ValueError(f"cycle among {stuck}")
    return order

Common mistakes

• "I evaluate cells row by row." (wrong) A cell may read one that comes later. (right) "I evaluate in topological order from the dependency graph."
• "On every edit I recompute the whole sheet." (wrong) That does work the edit cannot affect. (right) "I mark the cells reachable from the edit as dirty and recompute only those."
• "My cycle check prints every cell the sort could not finish." (wrong) That includes cells merely downstream of the loop. (right) "I report the path a depth-first search finds, and treat the leftovers as blocked."
• "If a value is unchanged, Excel skips the dependents." (wrong) Its documentation describes no such cutoff. (right) "Excel keeps recalculating dependents; my engine can add a cutoff as an improvement."
• "A volatile function only recalculates its own cell." (wrong) Its direct dependents follow. (right) "I treat a volatile cell as a dirty root at each recalculation and mark its dependents from it."

Follow-up questions

How do you implement spreadsheet-style cell notation where formulas reference other cells?

Parse each formula into the cell names it reads, store them in a precedents map and a dependents map, evaluate in topological order, and on an edit recompute the cells reachable through the dependents map. See the hub of industry coding problems for similar applied questions.

How do you detect circular references between cells?

Run Kahn's algorithm: if fewer cells are emitted than exist, a cycle blocks the rest. To report the loop, run a depth-first search that follows the precedents map and return the path when it reaches a cell already on the current path.

Does Excel recalculate the whole workbook on every edit?

No. It marks the dependents of changed cells as dirty and recalculates those, plus volatile functions, per Microsoft Learn. A full calculation is the exception.

What if the recomputed value did not change?

Excel still recalculates dependents. A cutoff engine stops there, which on the worked sheet saves one of five evaluations.¹

How would you implement an Excel-style engine with caching and invalidation?

Cache each cell's value, mark dirty cells as invalid on an edit, and clear the flag on recomputation. A dirty bit per cell is the standard idea: Mokhov et al. (2018) describe skipping a key only when it and all its transitive dependencies are clean. For expiry-based invalidation, see time-to-live caches and time-based key-value stores.

How do you resolve an install order for libraries with prerequisites?

Make each package a node and draw an edge from each prerequisite to the package that needs it, then run Kahn's algorithm: the emitted order is a valid install order, and a cycle leaves packages that can never be installed. For a "how many can be installed" variant, count the target packages whose whole prerequisite closure is reachable from available packages and contains no cycle.

Sources

1. Excel Recalculation — Microsoft Learn (Office client developer documentation), 26 Oct 2026
2. Excel performance: Improving calculation performance — Microsoft Learn (VBA documentation), 26 Oct 2026
3. Volatile Excel Functions — Decision Models (Charles Williams), 26 Oct 2026
4. graphlib: Functionality to operate with graph-like structures — Python Software Foundation, 26 Oct 2026
5. Build Systems à la Carte — Microsoft Research (Mokhov, Mitchell, Peyton Jones; ICFP 2018), 1 Sep 2018