Question presented to candidate:
"Build a small Excel: a grid of cells with column letters and row numbers. A cell holds a number, some text, or a formula such as =A1+B2 or =SUM(A1:A3). When a cell changes, everything that depends on it updates. Do not use eval, and do not freeze or crash when someone types a circular formula."
Requirements:
- A 5 x 8 grid (A to E, 1 to 8) with a formula bar showing the raw content of the selected cell.
- Formulas: numbers, cell references,
+ - * /, parentheses, unary minus, andSUM,AVERAGE,MIN,MAXover ranges and arguments. - Errors shown in the cell:
#DIV/0!,#NAME?(unknown function),#REF!(outside the grid),#VALUE!(text in arithmetic),#ERROR!(syntax),#CYCLE!(circular reference). - Changing a cell recalculates only that cell and its dependents, in dependency order; show the recalculation order.
- Excel-like editing: click to select, type to start editing, Enter commits and moves down, Tab commits and moves right, Escape cancels, arrows move the selection, Delete clears.
What a strong answer should cover:
- A tokenizer and a recursive-descent parser that builds an AST with correct precedence, evaluated by a small interpreter: never
evalornew Function. - A dependency graph (cell to the cells it reads) and its reverse (cell to the cells that read it).
- Recalculation as a topological sort of the dirty set (the edited cell plus its transitive dependents), for example with Kahn's algorithm.
- Cycle detection that falls out of the topological sort (nodes that never reach in-degree 0), marking those cells instead of recursing forever.
- Keeping the engine framework-free and telling the UI to re-read it after each commit.
Clarifying questions expected:
- "Which functions and operators must be supported, and should text be allowed in cells?"
- "How should errors look, and should an error propagate to dependent cells?"
- "Do we need absolute references like
$A$1, copy and paste, or undo?"
Code / implementation expected: Yes. The parser, the dependency-aware recalculation and an editable grid.