Katkat
Back

Design Spreadsheet Formula Cells

HarveySoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates ability to design and implement data structures and algorithms for expression parsing, dependency tracking, incremental evaluation, and cycle detection in an in-memory spreadsheet.

Design an in-memory spreadsheet that supports assigning either literal integer values or formulas to cells.

Cells are identified by names such as A1, B1, and C12. A formula is an expression made of cell references and integer constants joined by +, for example:

A1 = B1 + C1 + 5

Implement an API similar to:

setCell(cellName, valueOrFormula)
getCell(cellName) -> int

Requirements:

  1. setCell may assign either:
  • an integer value, such as 10, or
  • a formula, such as B1 + C1.
  1. getCell returns the current evaluated integer value of the requested cell.
  2. If a referenced cell has not been assigned, treat its value as 0.
  3. When a cell is updated, future reads should reflect the updated dependencies.
  4. Follow-up: detect circular dependencies between formulas and reject updates that would create a cycle. For example, the following should be rejected because it creates a cycle:
A1 = B1 + C1
C1 = A1

Explain your data structures and implement the API.