Design Spreadsheet - Practice Coding Problems

Design Spreadsheet - Problem

A spreadsheet is a grid with 26 columns (labeled from 'A' to 'Z') and a given number of rows. Each cell in the spreadsheet can hold an integer value between 0 and 10^5.

Implement the Spreadsheet class:

Spreadsheet(int rows) Initializes a spreadsheet with 26 columns (labeled 'A' to 'Z') and the specified number of rows. All cells are initially set to 0.
void setCell(String cell, int value) Sets the value of the specified cell. The cell reference is provided in the format "AX" (e.g., "A1", "B10"), where the letter represents the column (from 'A' to 'Z') and the number represents a 1-indexed row.
void resetCell(String cell) Resets the specified cell to 0.
int getValue(String formula) Evaluates a formula of the form "=X+Y", where X and Y are either cell references or non-negative integers, and returns the computed sum.

Note: If getValue references a cell that has not been explicitly set using setCell, its value is considered 0.

Input & Output

Example 1 — Basic Operations

$ Input: [["Spreadsheet",3],["setCell","A1",5],["setCell","B2",3],["getValue","=A1+B2"],["resetCell","A1"],["getValue","=A1+B2"]]

› Output: [null,null,null,8,null,3]

💡 Note: Create 3-row spreadsheet, set A1=5 and B2=3, A1+B2=8, reset A1 to 0, now A1+B2=3

Example 2 — Formula with Constants

$ Input: [["Spreadsheet",2],["setCell","A1",10],["getValue","=A1+5"],["getValue","=2+3"]]

› Output: [null,null,15,5]

💡 Note: Set A1=10, formula A1+5=10+5=15, formula 2+3=5

Example 3 — Unset Cell Reference

$ Input: [["Spreadsheet",1],["getValue","=A1+B1"]]

› Output: [null,0]

💡 Note: Both A1 and B1 are unset, so they default to 0: 0+0=0

Constraints

1 ≤ rows ≤ 1000
Cell references are valid format (A-Z)(1-rows)
0 ≤ cell values ≤ 10⁵
Formulas contain exactly 2 operands with '+' operator

Visualization

Tap to expand

Understanding the Visualization

Initialize

Create empty spreadsheet with specified rows

Set Cells

Store values in specific cell references

Calculate

Evaluate formulas by parsing and summing operands

Key Takeaway

🎯 Key Insight: Store only modified cells in a hash map to save memory and achieve O(1) operations

Asked in

G Google 35 M Microsoft 28 a Amazon 22 A Apple 18

The key insight is to efficiently store and retrieve cell values while parsing cell references and formulas. The hash map approach is optimal for sparse spreadsheets, storing only set cells. Time: O(1) per operation, Space: O(k) where k is the number of set cells.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Storage	O(1)	O(k)	Store only non-zero cells in a hash map using cell reference as key
2D Array Storage	O(1)	O(rows)	Store all cells in a 2D array of size 26 × rows

Hash Map Storage — Algorithm Steps

Create empty hash map
Store cell references as keys with their values
For formulas, look up cell values in map (default 0 if not found)

Visualization

Tap to expand

Step-by-Step Walkthrough

Empty Map

Hash map starts empty

Store Set Cells

Only cells with values are stored

Formula Lookup

Look up cell values, default to 0 if not found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_CELLS 1000

typedef struct {
    char cell[10];
    int value;
} CellEntry;

typedef struct {
    int rows;
    CellEntry cells[MAX_CELLS];
    int cellCount;
} Spreadsheet;

Spreadsheet* createSpreadsheet(int rows) {
    Spreadsheet* s = malloc(sizeof(Spreadsheet));
    s->rows = rows;
    s->cellCount = 0;
    return s;
}

void setCell(Spreadsheet* s, char* cell, int value) {
    // Find existing cell or add new one
    for (int i = 0; i < s->cellCount; i++) {
        if (strcmp(s->cells[i].cell, cell) == 0) {
            s->cells[i].value = value;
            return;
        }
    }
    strcpy(s->cells[s->cellCount].cell, cell);
    s->cells[s->cellCount].value = value;
    s->cellCount++;
}

void resetCell(Spreadsheet* s, char* cell) {
    for (int i = 0; i < s->cellCount; i++) {
        if (strcmp(s->cells[i].cell, cell) == 0) {
            // Remove by shifting remaining elements
            for (int j = i; j < s->cellCount - 1; j++) {
                s->cells[j] = s->cells[j + 1];
            }
            s->cellCount--;
            return;
        }
    }
}

int getCellValue(Spreadsheet* s, char* cell) {
    for (int i = 0; i < s->cellCount; i++) {
        if (strcmp(s->cells[i].cell, cell) == 0) {
            return s->cells[i].value;
        }
    }
    return 0; // Default value
}

int getValue(Spreadsheet* s, char* formula) {
    char* expr = formula + 1; // Skip '='
    int total = 0;
    char* part = strtok(expr, "+");
    
    while (part != NULL) {
        if (isdigit(part[0])) {
            total += atoi(part);
        } else {
            total += getCellValue(s, part);
        }
        part = strtok(NULL, "+");
    }
    
    return total;
}

int main() {
    printf("[null,null,null,5,null,7]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Hash map operations are constant time on average

✓ Linear Growth

Space Complexity

O(k)

Only stores k cells that have been explicitly set, not all possible cells

✓ Linear Space

25.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Storage — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler