2dbi
Home/Airtable/Topological Sort (Cell Dependencies)
AAirtable·DSASDE-2Technical Phone Screen

Topological Sort (Cell Dependencies)

Problem

Cells form a dependency graph (A depends on B). Given dependencies, compute a valid recompute order; detect cycles.

Example

A->B, B->C => recompute C,B,A; A->B,B->A -> cycle

Constraints

  • Up to 10^4 cells

What Airtable looks for

Core to Airtable's formula engine. Kahn's algorithm + cycle detection. Reported theme.

added 6 days ago
LeadersAccount