System Design #15: Design a Spreadsheet / Data Grid

interface VirtualGrid {
  // Viewport
  scrollTop: number;
  scrollLeft: number;
  viewportWidth: number;
  viewportHeight: number;
  
  // Dimensions
  rowHeights: number[];       // Variable heights per row
  columnWidths: number[];     // Variable widths per column
  
  // Computed visible range
  visibleRows: { start: number; end: number };
  visibleColumns: { start: number; end: number };
  
  // Overscan (render a few extra rows/cols for smooth scrolling)
  overscanRows: number;       // Default: 3
  overscanColumns: number;    // Default: 2
}

function getVisibleRange(
  scrollOffset: number,
  viewportSize: number,
  sizes: number[],
  overscan: number
): { start: number; end: number } {
  let accumulated = 0;
  let start = 0;
  let end = 0;
  
  // Find first visible item
  for (let i = 0; i < sizes.length; i++) {
    if (accumulated + sizes[i] > scrollOffset) {
      start = Math.max(0, i - overscan);
      break;
    }
    accumulated += sizes[i];
  }
  
  // Find last visible item
  accumulated = 0;
  for (let i = start; i < sizes.length; i++) {
    accumulated += sizes[i];
    if (accumulated > scrollOffset + viewportSize) {
      end = Math.min(sizes.length - 1, i + overscan);
      break;
    }
  }
  
  return { start, end: end || sizes.length - 1 };
}

DataGrid
├── GridHeader                    // Sticky column headers
│   ├── ColumnHeader[]            // Sortable, resizable
│   └── ColumnResizeHandle[]
├── GridBody                      // Virtualized content area
│   ├── RowNumberColumn           // Sticky row numbers (1, 2, 3...)
│   └── VirtualCells              // Only rendered cells
│       └── Cell                  // Individual cell
│           ├── CellDisplay       // Read-only view
│           └── CellEditor        // Active editing input
├── SelectionOverlay              // Blue selection rectangle(s)
├── ScrollbarX / ScrollbarY       // Custom scrollbars
├── FormulaBar                    // Shows active cell formula
└── StatusBar                     // "SUM: 42, AVG: 7, COUNT: 6"

// Don't store 100K × 50 cells in memory — most are empty!
// Use sparse storage: only store cells that have values

type CellKey = string; // "A1", "B2", etc. or "r0c0", "r1c1"

interface CellData {
  value: any;                    // Raw value (number, string, boolean)
  formula?: string;              // "=SUM(A1:A10)"
  displayValue?: string;         // Computed/formatted display text
  format?: CellFormat;
  style?: CellStyle;
}

interface CellFormat {
  type: 'text' | 'number' | 'date' | 'currency' | 'percentage';
  pattern?: string;              // "#,##0.00", "MM/dd/yyyy"
  locale?: string;
}

interface CellStyle {
  bold?: boolean;
  italic?: boolean;
  textColor?: string;
  bgColor?: string;
  alignment?: 'left' | 'center' | 'right';
}

// Sparse data store
class SpreadsheetData {
  private cells = new Map<CellKey, CellData>();
  
  getCell(row: number, col: number): CellData | null {
    return this.cells.get(`r${row}c${col}`) || null;
  }
  
  setCell(row: number, col: number, data: CellData): void {
    const key = `r${row}c${col}`;
    if (data.value === null && !data.formula && !data.style) {
      this.cells.delete(key); // Remove empty cells
    } else {
      this.cells.set(key, data);
    }
  }
  
  getCellCount(): number {
    return this.cells.size; // Only non-empty cells
  }
}

interface SelectionState {
  activeCell: CellRef;           // Current "focused" cell
  ranges: CellRange[];           // Selected ranges (can be multiple with Ctrl)
  isEditing: boolean;            // Cell editor is active
  editValue: string;             // Current editor content
  selectionMode: 'idle' | 'selecting' | 'extending';
}

interface CellRef {
  row: number;
  col: number;
}

interface CellRange {
  start: CellRef;
  end: CellRef;
}

function selectionReducer(state: SelectionState, action: SelectionAction): SelectionState {
  switch (action.type) {
    case 'CLICK_CELL':
      return {
        ...state,
        activeCell: action.cell,
        ranges: [{ start: action.cell, end: action.cell }],
        isEditing: false,
      };
      
    case 'SHIFT_CLICK_CELL':
      // Extend current selection
      const lastRange = state.ranges[state.ranges.length - 1];
      return {
        ...state,
        ranges: [
          ...state.ranges.slice(0, -1),
          { start: lastRange.start, end: action.cell },
        ],
      };
      
    case 'CTRL_CLICK_CELL':
      // Add new selection range
      return {
        ...state,
        activeCell: action.cell,
        ranges: [...state.ranges, { start: action.cell, end: action.cell }],
      };
      
    case 'DOUBLE_CLICK_CELL':
      return {
        ...state,
        activeCell: action.cell,
        isEditing: true,
        editValue: getCellDisplayValue(action.cell),
      };
      
    case 'ARROW_KEY':
      if (state.isEditing) return state; // Don't navigate while editing
      const next = moveCell(state.activeCell, action.direction);
      return {
        ...state,
        activeCell: next,
        ranges: [{ start: next, end: next }],
      };
      
    case 'ENTER':
      if (state.isEditing) {
        // Confirm edit and move down
        commitEdit(state.activeCell, state.editValue);
        const below = { row: state.activeCell.row + 1, col: state.activeCell.col };
        return { ...state, isEditing: false, activeCell: below, ranges: [{ start: below, end: below }] };
      }
      // Start editing
      return { ...state, isEditing: true, editValue: '' };
      
    case 'TAB':
      // Move right (or to next row start)
      const nextTab = state.activeCell.col < maxCol
        ? { row: state.activeCell.row, col: state.activeCell.col + 1 }
        : { row: state.activeCell.row + 1, col: 0 };
      return { ...state, activeCell: nextTab, ranges: [{ start: nextTab, end: nextTab }], isEditing: false };
      
    case 'ESCAPE':
      return { ...state, isEditing: false };
  }
}