Build a spreadsheet

Why build a tree instead of working the value out while you read the formula?

Because the second requirement asks the formula a question that a number cannot answer. Once =A1+B2*2 has been reduced to 14 while the characters were being read, nothing is left that knows it mentioned A1 and B2, and the dependency graph stage 3 needs cannot be built without re-scanning the text. The tree costs three small frozen dataclasses, and it makes the function that answers “which cells does this read” six lines long. If the spec really stopped at one cell with no references, evaluating as you go would be the right call, and saying that out loud is part of the answer.

How do three parsing functions produce operator precedence?

By the order in which they call each other, and nothing else. There is no precedence table anywhere in the code. The expression function handles + and -, and for each operand it calls the term function; the term function handles * and /, and for each operand it calls the factor function. So a term is always fully consumed before the expression level gets to look at the next +, which means the multiplication in 1+2*3 is finished and packaged before the addition is built. Adding a level, say exponentiation, means adding a function between term and factor and changing nothing else.

Should =7/2 be 3.5 or 3?

Decide it out loud, then test it. This build uses true division, so 7/2 is 3.5 and the value of a cell is an int or a float. A spreadsheet is a tool for arithmetic that people check by hand, and floor division would make =1/3*3 come out as zero, which no user would accept. The cost is float behaviour: 0.1+0.2 is not 0.3, and a build that had to be exact to the penny would use integer minor units or decimal.Decimal instead. Naming that trade-off is worth more in the round than either choice.

How do you stop a formula from depending on itself?

Walk the dependency graph before writing anything. Given the cells the new formula reads, follow what each of those reads, and what those read, and so on: if the walk ever reaches the cell being set, the formula would close a loop and the set is refused. That is a plain reachability search with a visited set, the same one graph traversal uses, run against the proposed edges while the sheet is still untouched. The detail candidates miss is the order: check first, write second. Writing the formula and then checking leaves a rejected formula in the sheet, and it surfaces two operations later as a wrong number.

Can anyone really write all of this in fifty minutes?

Not all three stages, and the interviewer does not expect it. Stage 1 is about a hundred and ten lines and takes a fluent candidate twenty-five minutes, because the tokenizer and the three parsing functions are muscle memory once you have written them twice. Stage 2 is the smallest of the three: a node type, two branches and a parameter. Stage 3 is another seventy lines and is where most rounds run out of clock, so the order matters: the cycle check before the incremental recompute, because rejecting a bad set is correctness and recomputing only the affected cells is performance. If the clock dies, say which one you would build next and why.