OpenAI VO 面试真题#3 用 DFS 实现电子表格依赖计算 —— Spreadsheet with Cells – 一亩三分地

Implement Spreadsheet with Cells

You are asked to design a simple Spreadsheet system consisting of multiple cells, where each cell can either contain a numeric value or depend on other cells by referencing them as children.

Each cell can be represented as an object:

class Cell {
    Integer value;
    String child1;
    String child2;
}

If a cell contains a value, it’s a constant.
If it contains one or two child references, its value equals the sum of its children.

You are required to implement a class Spreadsheet that supports:

1. Setting a cell with either a value or children references.
2. Getting the calculated value of a given cell key.

Example

Input:

setCell("A", new Cell(null, "B", "C"));
setCell("B", new Cell(3, null, null));
setCell("C", new Cell(5, null, null));

getCellValue("A") → 8

If cells have nested references:

setCell("A", new Cell(null, "B", "C"));
setCell("B", new Cell(null, "D", null));
setCell("C", new Cell(2, null, null));
setCell("D", new Cell(4, null, null));

getCellValue("A") → 6

Follow-up

1. In the first version, implement it using DFS traversal to recursively compute values.
2. In the optimized version, introduce a cache (memoization) to avoid recomputation and improve performance.
3. Further enhancement: maintain a parent map to update dependencies efficiently when a child value changes.

设计一个简单的电子表格系统（Spreadsheet），每个单元格（Cell）可以：

• 要么存一个固定数值；
• 要么依赖其他单元格的值（最多两个 child）。

若一个单元格有 child1 和 child2，它的值等于这两个单元格的和。
程序需要支持：

1. setCell(key, cell) —— 设置某个单元格；
2. getCellValue(key) —— 获取单元格的最终值（递归求和）。

举例：

A = B + C
B = 3
C = 5
→ getCellValue(A) = 8

若存在嵌套依赖：

A = B + C
B = D
C = 2
D = 4
→ getCellValue(A) = 6

第一版可直接用 DFS 从 key 递归计算值。

第二版引入 cache 来缓存中间结果，避免重复遍历。

若要支持动态更新，可维护一个 parent map，当某个 cell 改变时，沿依赖链向上更新。

VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 OpenAI、Google、Amazon、Citadel、SIG 等，提供实时语音助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Stripe 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。