Collaborative Spreadsheet System Design Interview: Formula Graphs and Concurrent Edits

Two users edit different cells, so their changes appear independent. One sets A1 to =B1+1; the other sets B1 to =A1+1. Each edit is valid against the old workbook, but together they create a cycle. That is the central challenge in a collaborative spreadsheet system design interview: agreement on edit order is only part of correctness.

Design the formula graph, mutation semantics, and revisioned calculation contract together. Use Design a collaborative spreadsheet backend to practise the discussion before choosing a synchronization technology.

Evidence boundary: HyperFormula's official documentation supports dependency graphs and spreadsheet reference behavior. The concurrent-edit protocol, workbook examples, and architecture below are original design proposals. They do not describe an employer's interview process or claim that one collaboration algorithm solves every spreadsheet invariant.

Define what a workbook revision contains

Begin with a narrow product: shared sheets containing typed values and a specified formula subset, online edits, reconnect, and visible calculation errors. Ask whether structural operations, offline editing, external data functions, and iterative circular calculations are required. These features change the consistency problem.

A committed revision should identify cell content and structural state. Computed values should identify the revision and calculation context they represent. Otherwise a client may display the formula from revision 42 beside the result from revision 41 without any indication that recalculation is pending.

Separate raw content from derived value. A formula string, parsed expression, dependencies, computed result, and error status are different fields. Persisting only the displayed number loses the formula; persisting only the formula forces every read to rediscover dependencies and execution state.

Use stable sheet and cell identities internally where structural changes demand them. User-facing A1 addresses are coordinates, not necessarily permanent identities. The design must define how insertion, deletion, copying, and moving affect references rather than assuming every operation is a plain string replacement.

Represent dependencies in both directions

HyperFormula documents a dependency graph so referenced values are processed before the formulas that need them. It also describes range nodes and reuse for overlapping ranges. These mechanisms are a useful reference, rather than a requirement to copy that engine's exact internal representation. HyperFormula dependency graph.

For this article's proposed representation, draw a forward edge from a precedent to its dependent: A1→B1 means B1 reads A1. Keep reverse indexes as well so a formula can find its precedents during evaluation. State the direction explicitly; otherwise cycle detection and invalidation explanations can sound correct while traversing the wrong graph.

Consider A1=2, A2=3, B1=SUM(A1:A2), C1=B1*2, and D1=A2+10. The initial computed values are B1=5, C1=10, and D1=13. Changing A1 to 4 dirties B1 and C1, but not D1. Changing A2 dirties all three derived cells.

An invalidation traversal finds affected descendants. Evaluation then uses an order in which required inputs are ready. If the affected subgraph has V nodes and E explicit edges, ordinary traversal and topological processing cost O(V+E), excluding formula execution, range representation, and external operations. A million-cell range should not disappear inside the phrase “constant-time recalculation.”

Replace a formula as one semantic mutation

Suppose B1 changes from SUM(A1:A2) to A1*3. The system must remove B1's old dependency on A2, install its new parsed expression, and mark affected descendants dirty. If obsolete edges remain, later A2 changes cause unnecessary work and may create misleading cycle reports.

A recommended commit procedure parses and validates the proposed expression, derives references, checks the resulting graph, then atomically publishes the cell content and graph change. Only the committed revision becomes visible as authoritative. A parse failure must not leave half the old graph and half the new content installed.

For large workbooks, you may validate incrementally rather than copying the whole graph. Replacing one formula's precedent edges changes a bounded part of the graph, but cycle checks can still touch many nodes. Give the worst-case scope instead of claiming every edit is local.

If the product allows formulas that return dynamic references, static extraction may not reveal all dependencies. Restrict the initial function set, track runtime dependencies with clear invalidation rules, or conservatively mark broader regions dirty. That choice affects both performance and correctness.

Trace concurrent edits that create a cycle

Initially A1 and B1 are literals. Client X submits A1=B1+1 based on revision 10. Client Y submits B1=A1+1, also based on revision 10. Both clients may optimistically preview a valid result using their old local state.

In a server-ordered design, X commits as revision 11. Y's operation must then be validated against revision 11, where adding B1's dependency on A1 closes a cycle. The server can reject Y or commit the expression with an explicit circular-reference error, depending on the product contract. Whichever policy you choose, return a consistent workbook revision and a visible outcome.

Observed state	Required decision
X's edit alone against revision 10	Valid dependency from B1 to A1.
Y's edit alone against revision 10	Valid dependency from A1 to B1.
Y arrives after X commits	Revalidate the combined graph; it contains a cycle.
Y reconnects after rejection	Return authoritative content, revision and rejection reason.

HyperFormula explicitly distinguishes a cyclic-dependency error in its ErrorType reference. That engine-level error is separate from whether the collaboration protocol accepts the edit.

A CRDT can make replicas converge on cell expressions while the resulting workbook still contains a circular dependency. An operation transformation system can preserve structural intent while formulas still produce errors. Synchronization and formula semantics need separate contracts.

If you choose local-first convergence, decide whether cycles are representable states. Deterministic error evaluation can preserve convergence, whereas independent rejection decisions at different replicas can diverge unless they follow an agreed protocol. Do not promise offline edits, global invariant enforcement, and immediate availability without explaining their tension.

Specify same-cell conflicts and meaningful undo

Two users replacing the same formula need an explicit resolution rule. A server sequence can make the later accepted replacement authoritative; a compare-and-swap version can instead return a conflict. Wall-clock timestamps from clients are a poor substitute for a defined ordering authority.

An operation record can carry operation ID, workbook ID, actor, base revision, target cell, mutation type, and payload. The server stores accepted sequence and outcome. Retries with the same operation ID return the previous result, while a reused ID with different payload is rejected.

Undo should reverse the user's operation in the current collaborative context, not blindly restore an old workbook snapshot. If X changes A1 from 2 to 4 and Y later changes it to 7, X's undo should not automatically erase Y's edit. Conditional inverse operations or a product-specific conflict notice make the behavior reviewable.

For structural changes, an undo can restore deleted rows and their identities, but references and later edits may require additional transformation. Keep tombstones or sufficient history for the supported retention period. Explain what happens when an operation is too old to invert safely.

What happens when rows move or ranges grow?

Copying =A1+$B$1 one row down shifts the relative reference but preserves the absolute one. Inserting a row is a different operation from copying a formula. Mixed references and cross-sheet addresses add more cases. HyperFormula's reference documentation is an official source for the distinctions; your collaboration protocol still has to apply them consistently. Cell references.

Represent structural edits as semantic operations. A row insertion changes coordinate mapping and may expand a range under the product's defined rules. Apply that transformation at the same committed revision as the structure change, then update dependency indexes. Raw search-and-replace over formula text can corrupt quoted strings or unrelated addresses.

A range like SUM(A1:A1000000) also demands a performance model. Range nodes, interval indexes, or aggregate structures can avoid maintaining a million separate edges for every overlapping sum. Different functions have different composability; a reusable partial sum does not automatically accelerate arbitrary custom functions.

Define deletion behavior. A deleted precedent can yield a reference error, preserve a tombstoned identity for undo, or follow explicit relocation semantics. Returning zero for every missing reference is convenient but can hide a damaged financial model.

Bound recalculation and isolate formula execution

A fast edit acknowledgement need not wait for every derived cell. Commit the mutation, mark calculations pending for a revision, and send results when they are ready. Clients should know whether a value is final, stale, or still computing.

A recommended worker task contains workbook revision, affected region, formula-engine version, and required snapshot context. Results are accepted only for the intended revision or an explicitly valid reuse case. If revision 44 finishes before revision 43, a late result from 43 must not overwrite 44's displayed value.

Volatile functions such as time or random values require a shared evaluation context if consistent results matter. Capture a calculation timestamp or seed according to the product's semantics. An external-data function additionally needs permissions, rate limits, timeout behavior, and a record of the data snapshot it used.

Never execute arbitrary formula text as host-language code. A parser and bounded interpreter should enforce supported functions, resource budgets, and access policy. Restrict network-enabled functions; a cell reference is not authorization to retrieve another tenant's data.

Design reconnect and recovery around accepted operations

A reconnecting client supplies its last acknowledged sequence and pending operation IDs. The server returns accepted deltas or a current snapshot plus the subsequent log. The snapshot must declare the sequence it includes so clients do not replay covered edits twice.

Presence and cursor location can tolerate loss; accepted cell edits require durable storage under the stated acknowledgement contract. Keep these paths separate. A user should not lose a formula because a presence server restarted.

If the calculator fails, rebuild the graph and derived values from committed workbook content and the recorded calculation contract. If content and graph are persisted separately, version them together and verify their agreement on recovery. A cache of computed values is useful, but should not be the only copy of cell intent.

Test two concurrent edits creating a cycle, duplicate submission, missing predecessor delta, reconnect after acknowledgement loss, undo after another actor's replacement, and row insertion affecting mixed references. Compare a full recalculation oracle with incremental results on small generated workbooks. That comparison catches stale-edge bugs better than checking one happy-path sum.

Practice formula and collaboration invariants

Use the engine exercises to prove a graph invariant, then use the design prompts to explain how concurrency changes it.

Question	Practice focus
Design a collaborative spreadsheet backend	Order edits and define acknowledged state.
Spreadsheet Formula Engine with Cycle Detection	Detect the combined cycle.
Spreadsheet Formulas with Dependency Updates	Remove obsolete dependency edges.
Design Extensible Undo and Redo for a Spreadsheet	Undo without erasing another actor.
Design a collaborative spreadsheet	Connect graph semantics with synchronization.

Begin with the formula-engine exercise. Draw the five-cell graph above, replace one formula, and trace the concurrent-cycle case. Your design should identify the commit point and the revision attached to every displayed result.

Sources and Further Reading

• HyperFormula: Dependency graph

• HyperFormula: Cell references

• HyperFormula: Error types

Primary references checked September 30, 2026. Product details and supported versions can change; the worked examples are original practice material.