Katkat
Back

Implement simplified Excel with SET/GET/SUM

Fuse EnergySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of data structures and algorithms for modeling and implementing a simplified spreadsheet, covering dependency graphs, formula evaluation, incremental updates, and cycle detection.

Implement a simplified in-memory spreadsheet that supports three operations: SET, GET, and SUM, similar to basic Excel functionality.

Assumptions and requirements:

  • The spreadsheet consists of cells identified by standard Excel-like coordinates:
  • Columns are single uppercase letters from 'A' to 'Z'.
  • Rows are integers from 1 to 1000.
  • A cell ID is a string such as 'A1', 'B2', 'Z1000'.
  • Each cell can either contain:
  • A numeric value (integer), or
  • A formula that is a sum of other cells or rectangular ranges of cells.

You must support the following operations:

  1. SET(cellId, value)
  • Set the given cell to a numeric integer value.
  • Any existing formula or previous value in that cell is overwritten.
  • Return the value set.
  1. GET(cellId)
  • Return the current evaluated integer value of the cell.
  • If the cell contains a formula (from a SUM operation), its value is the sum of its referenced cells, recursively evaluated.
  1. SUM(cellId, refs)
  • cellId is the target cell where we store a formula.
  • refs is a list of references. Each reference is either:
  • A single cell ID, e.g. 'B2', or
  • A rectangular range in the form 'A1:B2', which represents all cells whose column is between A and B inclusive and whose row is between 1 and 2 inclusive.
  • Store in cellId a formula that is defined as the sum of all cells in refs (expanding ranges into the constituent cells).
  • Return the evaluated sum of that formula.

Behavioral example (your implementation should be consistent with this behavior):

  • SET('A1', 1) → returns 1
  • SET('B2', 2) → returns 2
  • SUM('C1', ['A1:B2', 'B2']) → returns 5
  • SUM('C1', ['B2']) → returns 2
  • SET('C1', 5) → returns 5
  • GET('C1') → returns 5
  • SUM('D1', ['C1', 'A1']) → returns 6
  • SET('A1', 10) → returns 10
  • GET('C1') → returns 5 (SET('C1', 5) replaced C1's formula with the plain value 5, so changing A1 does not affect it)
  • GET('D1') → returns 15 (D1 is still the formula C1 + A1, now 5 + 10)

Additional requirements and edge cases:

  • Updating a cell via SET or SUM must correctly affect any other cells whose formulas depend (directly or transitively) on that cell, so that subsequent GET calls return up-to-date values.
  • There may be chains of dependencies, e.g. A1 used by B1, which is used by C1, etc.
  • You must handle potential cycles in formulas. For example, if A1 depends on B1 and later B1 is defined to depend on A1, there is a cycle.
  • Define and implement a reasonable behavior for cyclic dependencies (e.g., detect cycles during evaluation or update and prevent them, or return an error/special behavior). Clearly state your chosen behavior in code comments.
  • Aim for an efficient implementation that avoids recomputing large dependency graphs from scratch on every GET.

Design and implement the data structures and methods to support these operations.