OpenAI VO 面试真题 # 4 – Spreadsheet engine -一亩三分地 – 代面试 – 面试辅助

Design and implement a tiny Spreadsheet engine.

• Each cell is addressed by an ID such as A1, B1, …
• A cell can store either:
  1. an integer literal, e.g., 42, or
  2. a formula of the form X + Y, where X and Y are cell IDs (no minus/multiply in the base version).
• Implement:
  • setCell(id, valueOrFormula) — set a cell to an integer or to a formula string like "A1 + B1".
  • getCellValue(id) — return the evaluated integer value of the cell.

Rules / constraints

• A formula’s value is the sum of its referenced cells.
• Cells may depend on other cells transitively (A1 = B1 + C1, B1 = D1 + 3, etc.).
• You may assume inputs are valid in Part 1 (no cycles); a simple DFS that follows dependencies is acceptable.

Follow-ups

1. There will be many queries per second (getCellValue called frequently). Optimize beyond naïve DFS.
2. Allow updates to cells. When a cell changes, affected dependent cells should be recomputed efficiently.
3. (Optional) Detect cycles and report an error.
4. (Optional) Extend formula grammar to allow integer literals inside expressions (A1 + 3) and more operators.

Example

setCell("A1", 3)
setCell("B1", 5)
setCell("C1", "A1 + B1")
getCellValue("C1")  → 8

setCell("B1", "A1 + 1")   # C1 depends on B1 which depends on A1
getCellValue("C1")  → 7    # (A1=3, B1=4, C1=7)

实现一个迷你电子表格，单元格要么是整数，要么是形如 X + Y 的公式。支持设置与求值；后续要能高并发查询与增量更新。

基础做法（Part 1）

• 建图：每个 cell 记录它依赖的 children（最多两个）。
• getCellValue(id)：DFS 递归求值，memo 缓存一次求值结果，避免同次查询重复计算。

优化（Part 2）

• 维护 反向依赖图 parents：child -> {parents}。
• setCell 时：
  1. 解析新依赖，更新正反向图；
  2. 将受影响的所有节点做 失效(invalidate)（清空缓存）；
  3. 只在需要时重新计算（惰性求值）或采用 拓扑顺序 批量重算。
• 多次查询：保留 全局 memo 缓存；当没有变更时 get 为 O(1)。

可选增强

• 循环检测：在解析 / 更新时 DFS 加颜色标记（white/gray/black），发现回边即报错。
• 常数参与：允许 A1 + 3，解析时把常数作为叶子值处理。
• 错误处理：不存在的引用 / 重复定义 / 栈溢出等。

复杂度

• 单次查询（无更新）：O(依赖大小)，加 memo 后趋近于 O(1)。
• 更新：O(受影响子图大小)。

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