Quick Overview

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 simplified Excel with SET/GET/SUM

Company: Fuse Energy

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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. 2. **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. 3. **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 `14` (because `C1` still refers to `B2` whose value is `2`, so its formula sum is `2 + 10 + 2` in the example sequence) 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.

Quick Answer: 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 supporting three operations: SET, GET, and SUM. Cells use Excel-like coordinates: columns are single uppercase letters A..Z and rows are integers 1..1000 (e.g. "A1", "B2", "Z1000"). Each cell holds either an integer literal or a formula (a sum of referenced cells/ranges). An unset cell evaluates to 0. Drive the spreadsheet with a list of operations and return the result of each, in order: 1. SET(cellId, value): set the cell to an integer, overwriting any prior value/formula; return the value. 2. GET(cellId): return the cell's current evaluated integer value (recursively evaluating a formula). 3. SUM(cellId, refs): store a formula in cellId equal to the sum of all referenced cells. Each ref is either a single cell id ("B2") or a rectangular range ("A1:B2", all cells with column in [A,B] and row in [1,2]). Overwrites any prior value/formula; return the evaluated sum. Formula cells must reflect later updates to the cells they depend on (directly or transitively). You must handle cycles: if evaluating a cell re-enters that same cell, treat the re-entrant contribution as 0 so evaluation terminates and returns a finite integer. Input is a list of operation tuples (("SET", cell, value) / ("GET", cell) / ("SUM", cell, refs)); return a list of per-operation results.

Constraints

  • Columns are single uppercase letters A..Z.
  • Rows are integers 1..1000.
  • SET values are integers (may be negative).
  • A range "X1:Y2" includes all cells with column in [X,Y] and row in [1,2], inclusive.
  • SET and SUM both overwrite any prior literal or formula in the target cell.
  • An unset cell evaluates to 0.
  • Formulas may form cycles; a re-entrant cell contributes 0 during evaluation (evaluation always terminates).

Examples

Input: ([('SET','A1',1),('SET','B2',2),('SUM','C1',['A1:B2','B2']),('SUM','C1',['B2']),('SET','C1',5),('GET','C1'),('SUM','D1',['C1','A1']),('SET','A1',10),('GET','C1'),('GET','D1')],)

Expected Output: [1, 2, 5, 2, 5, 5, 6, 10, 5, 15]

Explanation: SUM C1 over A1:B2 (1+0+0+2) + B2 (2) = 5, then C1 is re-SUMmed to just B2 (2), then SET to literal 5. GET C1 = 5. D1 = C1(5)+A1(1) = 6. After SET A1=10, C1 is still a literal 5, so GET C1 = 5 and D1 = 5+10 = 15.

Input: ([('SET','A1',3),('SUM','B1',['A1']),('SUM','C1',['B1']),('GET','C1'),('SET','A1',7),('GET','C1')],)

Expected Output: [3, 3, 3, 3, 7, 7]

Explanation: Transitive chain C1->B1->A1. Initially C1 evaluates to 3. After SET A1=7, GET C1 re-evaluates the chain to 7, showing formulas reflect later updates.

Hints

  1. Keep two maps: cellId -> integer literal, and cellId -> list of constituent cell ids (a formula). A cell lives in at most one of them; SET/SUM should clear it from the other.
  2. Expand each SUM range into its constituent cell ids once, at SUM time, so GET only walks dependency edges instead of re-parsing ranges.
  3. Evaluate a formula recursively, summing the evaluated value of each constituent. Carry a visited set down the recursion; if you re-enter a cell already in it, return 0 to break the cycle.

Loading coding console...