spreadSheetIII
export default class Spreadsheet {
constructor() {
// Stores raw inputs by cell id. We store the original formula string instead
// of only the computed value because dependencies may change later.
this.cells = new Map();
}
/**
* Store or overwrite one cell.
*
* Interview explanation:
* setCell does not eagerly recompute dependent cells. We use lazy evaluation:
* values are calculated when getCell is called. This keeps writes simple and
* avoids needing a reverse dependency graph for invalidation.
*
* @param {string} cellId
* @param {number | string} input
* @returns {void}
*/
setCell(cellId, input) {
this.cells.set(cellId, input);
}
/**
* Return the current computed value of a cell.
*
* Interview explanation:
* Each getCell call creates fresh memo and activePath structures so the result
* always reflects the current spreadsheet state.
*
* @param {string} cellId
* @returns {number | '#CYCLE!'}
*/
getCell(cellId) {
// Each read uses fresh memo/path so evaluation reflects current sheet state.
return this.#evaluateCell(cellId, new Map(), new Set());
}
/**
* DFS evaluator for a cell.
*
* memo:
* Caches values already computed during this getCell call.
*
* activePath:
* Tracks the recursion stack. If we try to evaluate a cell already in this
* set, we found a cycle.
*
* Example cycle:
* A1 -> B1 -> C1 -> A1
* When evaluating C1 and resolving A1, A1 is still in activePath, so the
* engine returns '#CYCLE!'.
*
* @param {string} cellId
* @param {Map<string, number | '#CYCLE!'>} memo
* @param {Set<string>} activePath
* @returns {number | '#CYCLE!'}
*/
#evaluateCell(cellId, memo, activePath) {
// Reuse already-computed result in this evaluation pass.
if (memo.has(cellId)) {
return memo.get(cellId);
}
// Visiting the same cell again on current DFS path means a cycle.
if (activePath.has(cellId)) {
memo.set(cellId, '#CYCLE!');
return '#CYCLE!';
}
// Mark cell as currently being evaluated.
activePath.add(cellId);
const raw = this.cells.get(cellId);
if (raw === undefined) {
// Interview choice: unset cells behave as 0, similar to many spreadsheet
// coding interview variants.
memo.set(cellId, 0);
activePath.delete(cellId);
return 0;
}
if (typeof raw === 'number') {
// Numeric literals are base cases in the dependency graph.
memo.set(cellId, raw);
activePath.delete(cellId);
return raw;
}
if (!raw.startsWith('=')) {
// Fallback for non-formula strings; question guarantees valid inputs.
const parsed = Number(raw);
const value = Number.isNaN(parsed) ? 0 : parsed;
memo.set(cellId, value);
activePath.delete(cellId);
return value;
}
// Tokenize formula and evaluate strictly left-to-right.
// Example: "=A1 - 2 * 3" becomes ["A1", "-", "2", "*", "3"].
const expression = raw.slice(1).replace(/\s+/g, '');
const tokens = expression.match(/[A-Z]+\d+|\d+(?:\.\d+)?|[+\-*/]/g) || [];
// Resolve the first operand, then apply operator/right-operand pairs.
let result = this.#resolveOperand(tokens[0], memo, activePath);
if (result === '#CYCLE!') {
// Any cycle dependency makes the current cell a cycle result too.
memo.set(cellId, '#CYCLE!');
activePath.delete(cellId);
return '#CYCLE!';
}
for (let i = 1; i < tokens.length; i += 2) {
const operator = tokens[i];
const rightValue = this.#resolveOperand(tokens[i + 1], memo, activePath);
if (rightValue === '#CYCLE!') {
// Propagate cycle through dependent formulas.
memo.set(cellId, '#CYCLE!');
activePath.delete(cellId);
return '#CYCLE!';
}
if (operator === '+') {
result += rightValue;
} else if (operator === '-') {
result -= rightValue;
} else if (operator === '*') {
result *= rightValue;
} else {
result /= rightValue;
}
}
// Cache the computed result before returning so another cell in this same
// getCell call can reuse it.
memo.set(cellId, result);
// Done evaluating this branch.
activePath.delete(cellId);
return result;
}
/**
* Convert one formula token into a number.
*
* A token can be:
* - a numeric literal like "10" or "3.5"
* - a cell reference like "A1"
*
* @param {string} token
* @param {Map<string, number | '#CYCLE!'>} memo
* @param {Set<string>} activePath
* @returns {number | '#CYCLE!'}
*/
#resolveOperand(token, memo, activePath) {
// Operands are either numeric literals or cell references.
if (/^\d+(?:\.\d+)?$/.test(token)) {
return Number(token);
}
return this.#evaluateCell(token, memo, activePath);
}
}
/**
Test cases:
// 1) No cycle, left-to-right arithmetic.
const s1 = new Spreadsheet();
s1.setCell('A1', 10);
s1.setCell('B1', '=A1 - 2 * 3');
// (10 - 2) * 3 = 24
s1.getCell('B1'); // 24
// 2) Self-reference cycle.
const s2 = new Spreadsheet();
s2.setCell('A1', '=A1 + 1');
s2.getCell('A1'); // '#CYCLE!'
// 3) Direct cycle between two cells.
const s3 = new Spreadsheet();
s3.setCell('A1', '=B1 + 1');
s3.setCell('B1', '=A1 + 1');
s3.getCell('A1'); // '#CYCLE!'
s3.getCell('B1'); // '#CYCLE!'
// 4) Indirect cycle (A1 -> B1 -> C1 -> A1).
const s4 = new Spreadsheet();
s4.setCell('A1', '=B1 + 1');
s4.setCell('B1', '=C1 + 1');
s4.setCell('C1', '=A1 + 1');
s4.getCell('A1'); // '#CYCLE!'
// 5) Dependent on a cycle should also be cycle.
const s5 = new Spreadsheet();
s5.setCell('A1', '=B1 + 1');
s5.setCell('B1', '=B1 + 2');
s5.setCell('C1', '=A1 + 10');
s5.getCell('C1'); // '#CYCLE!'
*/
/**
* Interview question:
* Design a small spreadsheet engine.
*
* Requirements:
* - setCell(cellId, input) stores either a number or a formula string.
* - getCell(cellId) returns the computed value for that cell.
* - Formulas start with "=" and may reference other cells.
* - Support numeric literals and +, -, *, / operators.
* - Detect self, direct, and indirect cycles.
*
* Example:
* A1 = 10
* B1 = "=A1 + 5"
* getCell("B1") returns 15
*
* Core idea:
* Treat formulas as a dependency graph. Each cell can depend on other cells.
* Evaluating a cell is a DFS through that graph. `memo` avoids recomputing
* cells during one read, and `activePath` detects cycles in the current DFS path.
*
* Important simplification:
* This implementation evaluates formulas strictly left-to-right. It does not
* implement normal math precedence where * and / happen before + and -.
*
* Spreadsheet III: supports numeric literals and formulas with +, -, *, /,
* and detects direct/indirect/self cycles.
*
* If a cell is in a cycle, or depends on a cycle, getCell returns '#CYCLE!'.
*/