Character AI·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say

May 2026

Summary

System design round at Character AI for a software engineer role. The whole thing was one meaty question about building a spreadsheet engine, and they really wanted to dig into the internals rather than just get a working answer.

Questions Asked (1)

Design a spreadsheet data structure where cells can hold either literal values or formulas referencing other cells. Implement set_cell and get_cell, where get_cell recursively resolves formula dependencies. Cover the dependency graph representation, evaluation order, update propagation, cycle detection, and edge cases like self-references and missing cells. Also discuss memoization and lazy vs eager evaluation with time complexity for each operation.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

This one kept expanding.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and assumptions, then design a dependency graph using adjacency lists to model cell relationships. Implement lazy evaluation with memoization for get_cell and recursive DFS with cycle detection for set_cell, discussing trade-offs between lazy and eager approaches. Analyze time and space complexity for each operation and address edge cases like self-references and missing cells.

Pro tip: Emphasize that lazy evaluation with memoization is often preferred for spreadsheets because it avoids unnecessary computations and naturally handles cycles, but be prepared to discuss when eager evaluation might be beneficial for real-time updates.

1. Clarify Requirements and Assumptions

Ask about expected scale, update frequency, and whether formulas can reference ranges or only single cells. State assumptions like single-threaded environment and no range references for simplicity.

2. Design Data Structures

Represent each cell with a value or formula, and maintain a dependency graph (e.g., adjacency list) to track which cells depend on which. Consider storing reverse dependencies for efficient update propagation.

3. Implement Core Operations

For set_cell, update the cell and its dependencies, detecting cycles via DFS. For get_cell, recursively evaluate formulas with memoization to cache results and avoid redundant computation.

4. Handle Edge Cases and Errors

Address self-references, missing cells (return empty or error), and cycles (raise exception or return error value). Discuss how to propagate updates when a cell changes.

5. Analyze Trade-offs and Complexity

Compare lazy vs eager evaluation: lazy defers computation, saving time when cells aren't read, while eager updates all dependents immediately. Provide time complexity for set_cell and get_cell in both approaches.

Key Points to Mention

Dependency graph representation using adjacency lists (forward and reverse edges) for efficient traversal and update propagation.
Cycle detection using DFS with visiting states (unvisited, visiting, visited) to identify self-references and circular dependencies.
Memoization to cache evaluated cell values, reducing get_cell complexity from exponential to linear in the number of dependencies.
Lazy vs eager evaluation: lazy computes on demand with memoization, while eager recomputes dependents on each update; discuss trade-offs in time and space.
Time complexity: get_cell O(V+E) with memoization, set_cell O(V+E) for cycle check and update propagation; space O(V+E) for graph and cache.
Edge cases: missing cells return empty or error, self-references detected as cycles, and handling of formula errors (e.g., division by zero).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.