Cell Validation: Validate Spreadsheet Cell Values Against Type and Dependency Rules
Interview Experience
Problem
You are building a spreadsheet engine. Each cell has an ID (e.g., "A1"), a declared type (int, float, string, formula), and a value. Formula cells reference other cells (e.g., =A1 + B2). Implement a validator that checks: (1) type constraints, (2) formula reference validity (no references to undefined cells), and (3) circular dependency detection.
python
class SpreadsheetValidator:
def load(self, cells: dict[str, dict]) -> None:
"""
cells = {cell_id: {"type": str, "value": Any, "refs": list[str]}}
"""
def validate(self) -> list[str]:
"""Return list of error messages."""
Example:
cells = {
"A1": {"type": "int", "value": 42, "refs": []},
"B1": {"type": "formula", "value": "=A1+C1", "refs": ["A1","C1"]},
"C1": {"type": "formula", "value": "=B1", "refs": ["B1"]}
}
validate() -> ["Circular dependency: B1 -> C1 -> B1", "C1 references undefined A1? No..."]
Follow-ups
- How do you detect circular dependencies efficiently — DFS with coloring?
- If a formula cell's value must equal a specific type, how do you infer the return type of a formula?
- How would you compute evaluation order for valid formulas (topological sort)?
- What should happen when a referenced cell's type changes — how do you propagate re-validation?
Full Details
Problem
You are building a spreadsheet engine. Each cell has an ID (e.g., "A1"), a declared type (int, float, string, formula), and a value. Formula cells reference other cells (e.g., =A1 + B2). Implement a validator that checks: (1) type constraints, (2) formula reference validity (no references to undefined cells), and (3) circular dependency detection.
python
class SpreadsheetValidator:
def load(self, cells: dict[str, dict]) -> None:
"""
cells = {cell_id: {"type": str, "value": Any, "refs": list[str]}}
"""
def validate(self) -> list[str]:
"""Return list of error messages."""
Example:
cells = {
"A1": {"type": "int", "value": 42, "refs": []},
"B1": {"type": "formula", "value": "=A1+C1", "refs": ["A1","C1"]},
"C1": {"type": "formula", "value": "=B1", "refs": ["B1"]}
}
validate() -> ["Circular dependency: B1 -> C1 -> B1", "C1 references undefined A1? No..."]
Follow-ups
- How do you detect circular dependencies efficiently — DFS with coloring?
- If a formula cell's value must equal a specific type, how do you infer the return type of a formula?
- How would you compute evaluation order for valid formulas (topological sort)?
- What should happen when a referenced cell's type changes — how do you propagate re-validation?
About This Question
This is a candidate experience report from a sierra interview during the phone round.
It covers the following topics: Strings, Phone, Graph, Coding, Onsite .