How do you build an Excel formula engine in a coding interview?

In this article

1. Before you start
2. Why interviewers ask this
3. Spreadsheet formula engine 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 is one step of the data analyst interview path. It is a worked coding problem, explained in words, one small computed example and a short Python engine. The prerequisites box above lists the three ideas to know first.

Why interviewers ask this

A wrong recalculation shows a wrong number with no warning, and that is the consequence this round probes. The task is a compact version of a real engine: Microsoft documents that Excel does not calculate cells in a fixed order, or by row or column, and instead derives an order from the formulas' dependencies.

No public source documents which companies set this exercise or how they score it, so treat the scope below as a typical shape, not any company's rubric. A weak answer evaluates cells top to bottom and left to right, and recomputes everything on each edit. A strong answer builds a dependency graph, orders it with a topological sort, recomputes only what an edit touches and reports cycles. A Staff-level answer adds volatile functions, value cutoffs and parallel branches.

Analytics work meets the same ideas in Excel interview questions, in the calculated fields behind dashboard design questions, and in the declarative thinking of Structured Query Language (SQL) interview questions, where you also say what to compute, not the order.

Spreadsheet formula engine from first principles

Dependency graph

A dependency graph is a directed graph with one node per cell and an arrow from each precedent, a cell that a formula reads, to each dependent, the cell whose formula reads it, so the arrows show which cells must be calculated before which others and which must be calculated again after an edit.

Volatile function

A volatile function is a spreadsheet function whose result can change without any of its inputs changing, such as one that reads the clock or a random number, so the engine re-evaluates it, together with all its dependents, at every recalculation instead of only after an edit to something it reads.

Clarify the scope first

A formula engine is a large problem, so ask what is in scope before you write code. Useful questions: which operators are needed (plus, minus, times, divide, parentheses)? Are ranges and function calls in scope? What should an error, such as division by zero, a bad reference or a circular reference, do to the cells that read it? What does an empty cell read as? How do edits arrive, for example as a set_cell(name, content) call that returns the recalculated cells?

The assumptions this page states: numbers, cell references, + - * / and parentheses; an empty cell reads as 0; an edit replaces one cell's content and triggers a recalculation; errors are reported, not hidden. Ranges, functions and error propagation are treated as extensions, with one sentence each in the steps below.

In plain words

Think of a row of dominoes where each domino is a cell and some rest on several others. Knock one over and only the dominoes downstream fall, each after the ones it rests on. A formula engine works the same way: an edit topples only the cells downstream of it. The analogy breaks in one place. A domino falls once, but Excel may evaluate a formula more than once per recalculation, as Step 3 explains.

In one precise sentence, a formula engine keeps a dependency graph of the cells and, after an edit, evaluates the affected cells in an order where every cell comes after the cells it reads. The parser turns formula text into references and operators. The evaluator runs cells in topological order.

Text description of the diagram

• The parser turns formula text into references and operators.
• The evaluator runs cells in topological order.

Step 1: Store each cell as a constant or a formula

A cell holds either a constant value or the text of a formula, and the engine keeps one dictionary from cell name to content and another from cell name to current value. Keeping the formula text apart from the computed value matters: an edit replaces the text, and recalculation replaces the value.

Input: a cell name and new content. Output: the stored content, with the old formula's arrows marked for removal. Real Excel bounds this store. Microsoft's specifications and limits page lists 8,192 characters per formula, 64 nested function levels and 255 arguments per function. An interview engine may state caps of its own. You now have the data the parser needs.

Step 2: Parse each formula into the cells it reads

A tokenizer splits the formula text into numbers, cell references, operators, parentheses and function names. A syntax tree is a tree whose nodes are operators or values and whose children are their operands. A recursive-descent parser builds it with one function per precedence level, so multiplication binds tighter than addition.

Input: formula text. Output: a syntax tree plus the list of cell references found in it. That list is the cell's precedents. For each precedent, add an arrow to the dependents map. A range expands into its cells, so one formula adds one arrow per cell in the range. The grammar is this page's own design, not a documented Excel algorithm, so state your grammar before you code. You now know which cells feed which.

Step 3: Recalculate only the dirty cells in dependency order

After an edit, the recalculation set is the edited cell (if it now holds a formula), all its direct and indirect dependents, and the volatile cells with their dependents. Microsoft's recalculation documentation gives the example: if B1 depends on A1 and C1 depends on B1, changing A1 marks both B1 and C1 dirty. Find the dependents with a walk over the dependents map, starting at the edited cell. If the new formula creates a cycle, Kahn's count check catches it.

Topological sort is an algorithm that orders the nodes of a directed acyclic graph (DAG) so that every node comes before all the nodes it points to (Interview Cake). Kahn's algorithm is the usual version: count each cell's in-degree, the number of precedents it has, queue the cells at zero, and repeatedly remove one, lower its dependents' counts and queue any that reach zero (Kahn, 1962; AlgoMaster). It runs in O(V + E) time, where V is the cells and E the arrows.

Excel's own engine differs. If a formula's precedents are not yet calculated, Excel sends it down the calculation chain to be calculated again later, so a formula can be calculated several times per recalculation. Your engine evaluates each cell once.

Step 4: Keep volatile functions and unchanged values in mind

Excel re-evaluates cells that contain volatile functions, together with all their dependents, every time it recalculates (Excel recalculation page). That page lists the current-time, current-date, random-integer, offset and indirect-reference functions as volatile.

Implement it with a set of volatile cells: after each edit, add them and their dependents to the recalculation set. Excel also keeps calculating dependents when an upstream value did not change (calculation performance page). A value-change cutoff, which stops propagating once a recomputed value equals the old one, is a design choice for your engine, not Excel's behavior. Name it as an optimization and say what it costs: you must track which precedents actually changed.

Step 5: Detect a circular reference while ordering

A circular reference is a cell that depends on itself, directly or through other cells. Excel detects it and warns the user, and it allows deliberate ones only when iterative calculation is switched on (Excel recalculation docs). In graph terms it is a cycle, and only a DAG has a topological order.

Kahn's algorithm reports a cycle when it orders fewer cells than exist. Cells in the cycle never reach in-degree zero, and neither do their dependents, so the cells left unordered are the ones to mark with an error. A self-reference is caught the same way. Say in the interview whether your engine rejects the edit or accepts it and marks the error.

1 · Store cells2 · Parse formulas3 · Recalculate4 · Volatile cells5 · Detect cyclesReplay

Step-by-step description

1. A cell holds a constant or formula text.
2. The parser finds the cells each formula reads.
3. The edited cell and its dependents run once, in order.
4. Volatile cells and dependents join every pass.
5. Fewer cells ordered than exist means a cycle.

• The recalculation set is the edited cell plus its direct and indirect dependents.
• Kahn's algorithm reports a cycle when it orders fewer cells than exist.

Worked example

The toy sheet is illustrative: A1 holds 10, B1 is A1*2, C1 is B1+A1, D1 is a clock reading and E1 is D1+1.¹ The in-degrees for A1 to E1 are 0, 1, 2, 0 and 1. Kahn's algorithm, queuing ready cells in name order, gives the valid order A1, D1, B1, E1, C1.¹

With an illustrative stand-in clock value of 100, B1 is 20, C1 is 30 and E1 is 101. Now edit A1 to 15. The dirty cells are B1 and C1, evaluated in that order, giving 30 and 45.¹ Because D1 is volatile, D1 and E1 are recalculated too, so the order is B1, D1, C1, E1.¹ Dirty-only recalculation re-evaluates two cells after editing A1. Volatile cells add two more. A full recalculation would evaluate all four formulas.¹

The cycle sheet is also illustrative: A1 is B1+1 and B1 is A1+1. Both cells have in-degree 1, so none reaches zero. Kahn's algorithm orders 0 of 2 cells and reports a cycle.¹

Text description of the diagram

• Dirty-only recalculation re-evaluates two cells after editing A1.
• Volatile cells add two more.

The trace below draws the toy sheet's graph and the queue. Every cell is evaluated after the cells it reads. After editing A1 the recalculation order is B1, D1, C1 and E1.¹

1 · A1 first2 · D1 second3 · B1 after A14 · E1 after D15 · C1 last6 · The editReplay

Step-by-step description

1. A1 comes out first: in-degree 0.
2. D1 comes out second: in-degree 0.
3. B1 follows A1, which it reads.
4. E1 follows D1, which it reads.
5. C1 comes last, after A1 and B1.
6. After editing A1, B1, D1, C1, E1 recalculate.

• Every cell is evaluated after the cells it reads.
• After editing A1 the recalculation order is B1, D1, C1 and E1.

A short Python engine

The block below is a runnable version of the three pieces an interviewer expects. It holds three of the four maps in Step 1 and Step 2 (content, precedents, dependents) plus a value map.

import re
from collections import deque

TOKEN = re.compile(r"(\d+\.?\d*)|([A-Z]+\d+)|(.)")  # number | cell ref | operator
content, tree, prec, dep, value = {}, {}, {}, {}, {}

def parse(text):
    toks = [a or b or c for a, b, c in TOKEN.findall(text.replace(" ", ""))]
    pos = [0]
    def peek(): return toks[pos[0]] if pos[0] < len(toks) else None
    def take(): t = peek(); pos[0] += 1; return t
    def expr():                      # + and - : lowest precedence
        node = term()
        while peek() in ("+", "-"):
            op = take(); node = (op, node, term())
        return node
    def term():                      # * and / bind tighter
        node = atom()
        while peek() in ("*", "/"):
            op = take(); node = (op, node, atom())
        return node
    def atom():                      # number, reference or ( expr )
        t = take()
        if t == "(":
            node = expr(); take(); return node
        return ("num", float(t)) if t[0].isdigit() else ("ref", t)
    node = expr()
    if peek() is not None: raise ValueError("unexpected " + peek())
    return node

def refs(node):
    if node[0] == "ref": return [node[1]]
    if node[0] == "num": return []
    return refs(node[1]) + refs(node[2])

def ev(node):                        # an empty cell reads as 0
    k = node[0]
    if k == "num": return node[1]
    if k == "ref": return value.get(node[1], 0.0)
    a, b = ev(node[1]), ev(node[2])
    return a + b if k == "+" else a - b if k == "-" else a * b if k == "*" else a / b

def set_cell(name, text):
    for p in prec.get(name, []):     # drop the old arrows first
        dep[p].discard(name)
    content[name] = text
    if text.startswith("="):
        tree[name] = parse(text[1:]); prec[name] = sorted(set(refs(tree[name])))
    else:
        tree.pop(name, None); prec[name] = []; value[name] = float(text)
    dep.setdefault(name, set())
    for p in prec[name]:
        dep.setdefault(p, set()).add(name)

def recalc(starts, volatile=()):
    todo = set(starts) | set(volatile)           # edited cells + volatile cells
    stack = list(todo)
    while stack:                                  # add all direct and indirect dependents
        for d in dep.get(stack.pop(), ()):
            if d not in todo: todo.add(d); stack.append(d)
    indeg = {n: sum(p in todo for p in prec[n]) for n in todo}
    queue = deque(sorted(n for n in todo if indeg[n] == 0))
    order = []
    while queue:                                  # Kahn's algorithm on the set only
        n = queue.popleft(); order.append(n)
        for d in sorted(dep[n]):
            if d in todo:
                indeg[d] -= 1
                if indeg[d] == 0: queue.append(d)
    if len(order) < len(todo):                    # fewer ordered than exist: a cycle
        return [], sorted(todo - set(order))
    done = [n for n in order if n in tree]
    for n in done: value[n] = ev(tree[n])
    return done, []

Read it in three parts. parse is a recursive-descent parser: expr handles plus and minus, calls term for times and divide, which calls atom for numbers, references and parentheses, so multiplication binds tighter than addition. set_cell first removes the cell's old arrows from the dependents map, then stores the new content and adds one arrow per reference. recalc collects the edited cells, the volatile cells and every dependent, then runs Kahn's algorithm on just that set and evaluates each formula once. It returns the cells it evaluated, or the cells left unordered when there is a cycle.

The cost is O(V + E) over the recalculation set, plus the length of the formula for each parse. The sorted calls only make the order repeatable; drop them for strict linear time. Division by zero and bad references raise Python errors here; a fuller engine would store an error value and let dependents read it. Running it on the toy sheet gives the same dirty set and values as above.

The edit A1 = =E1/10, which turns a constant into a formula, puts A1 itself in the set, and the order becomes D1, E1, A1, B1, C1; a version that walked only the dependents would leave A1 stale.¹ The edit A1 = =C1+1 leaves A1, B1 and C1 unordered, so the function reports them as a cycle.¹

Trade-offs and edge cases

Which recalculation strategy to choose

The best strategy is to recalculate only the dirty cells, because it saves work while staying correct as long as the dependents map is accurate.

Smart recalculation has a cost of its own. Microsoft documents a ForceFullCalculation setting that turns smart recalculation off so every recalculation recalculates all formulas (calculation performance docs), which shows that tracking is not free. Excel offers three modes, Automatic, Automatic Except Tables and Manual (recalculation docs). In your engine, a manual mode should defer evaluation, not skip marking cells dirty.

Edge cases to mention

Replacing a formula must first remove its old arrows from the dependents map, or stale arrows trigger needless work and false cycles. Decide and state what an empty cell reads as. A very long chain overflows a recursive evaluator, so use Kahn's iterative loop. Topological order is not unique, so tests should check that every cell comes after its precedents, not one fixed order (AlgoMaster). Independent branches of the chain can run on separate threads, which Excel has done since Excel 2007. Last, a rebuild command exists in Excel, Ctrl+Alt+Shift+F9, which rebuilds the dependency tree and the chain and recalculates everything; a debugging tool in your engine can offer the same.

How to answer it in an interview

The spoken structure: name the two maps, say how you find the dirty set, give the ordering and its cost, then the cycle rule and your tests.

Common mistakes

• "I'll evaluate cells row by row, left to right." (wrong) Excel does not calculate by row or column, and a formula can read a cell below or to its right. (right) "I order cells by dependency with a topological sort."
• "Only the edited cell changes." (wrong) Direct and indirect dependents are marked dirty too. (right) "The set is the edited cell, if it holds a formula, plus all its dependents, plus volatile cells and their dependents."
• "A volatile function recalculates only itself." (wrong) It recalculates together with all its dependents. (right) "I add volatile cells and their dependents to every recalculation."
• "A cycle is always an error." (wrong) Excel allows deliberate circular references when iterative calculation is on. (right) "By default I flag the cycle; iteration would need a maximum count and a stop threshold."
• "The topological order is unique." (wrong) Several valid orders can exist. (right) "Any order where every cell follows its precedents is correct."

Follow-up questions

How do you detect a circular reference in a spreadsheet?

Run Kahn's algorithm and compare the number of cells ordered with the number of cells given. Fewer means a cycle, and the unordered cells are the cycle plus its dependents. A depth-first search also works but needs extra marking to catch cycles (AlgoMaster).

What is a volatile function and why does it slow recalculation?

A volatile function is re-evaluated at every recalculation, even when none of its inputs changed, and so are all its dependents. Many volatile functions slow each recalculation but make no difference to a full calculation (calculation performance docs).

Should recalculation stop when a value did not change?

Excel does not stop; it keeps calculating dependents even when the upstream value did not change. Your engine may add a cutoff to save work, but then it must track which precedents changed, and you should present it as an optimization with that cost.

How would you recalculate in parallel?

Cells with no dependency path between them can be evaluated at the same time, so the engine can run each ready group of the queue on separate workers. Excel documents the same idea: independent sections of its calculation chain can be calculated at the same time.

How would you trace a wrong number back to its source?

Walk the precedents instead of the dependents, from the wrong cell back to constants, and check each step. That is the same upstream hunt used in a metric dropped case.

Sources

1. Excel Recalculation — Microsoft Learn, Office client developer docs (accessed 2026-10-26), 18 Dec 2024
2. Excel performance: Improving calculation performance — Microsoft Learn, VBA docs (accessed 2026-10-26), 24 Jan 2024
3. Excel specifications and limits — Microsoft Support (undated page, accessed 2026-10-26), 26 Oct 2026
4. Topological sorting of large networks — Communications of the ACM 5(11) (Kahn), 1 Nov 1962
5. Topological Sort Algorithm: Kahn's and DFS — Interview Cake (undated page, accessed 2026-10-26), 26 Oct 2026
6. Introduction to Topological Sort — AlgoMaster (undated page, accessed 2026-10-26), 26 Oct 2026