Design Excel Sum Formula

hard design graph

Problem

Excel mock with set(r, c, v), sum(r, c, refs), get(r, c). Setting a cell removes its formula; sum stores the formula and returns the current sum.

Inputops: set(1,'A',1); sum(3,'C',['A1','A1:B2']); set(2,'B',2); get(3,'C')

Output1 (then) 4

Sum recomputes lazily.

input

class Excel:
    def __init__(self, h, w):
        self.g = [[0]*26 for _ in range(h+1)]; self.f = {}
    def set(self, r, c, v):
        self.g[r][ord(c)-65] = v; self.f.pop((r, c), None)
    def get(self, r, c):
        if (r, c) in self.f:
            tot = 0
            for tok in self.f[(r, c)]:
                if ':' in tok:
                    a, b = tok.split(':')
                    r1, c1 = int(a[1:]), ord(a[0])-65
                    r2, c2 = int(b[1:]), ord(b[0])-65
                    for rr in range(r1, r2+1):
                        for cc in range(c1, c2+1): tot += self.get(rr, chr(cc+65))
                else: tot += self.get(int(tok[1:]), tok[0])
            return tot
        return self.g[r][ord(c)-65]
    def sum(self, r, c, refs):
        self.f[(r, c)] = refs; return self.get(r, c)

class Excel {
  constructor(h, w) { this.g = Array.from({length: h+1}, () => new Array(26).fill(0)); this.f = new Map(); }
  set(r, c, v) { this.g[r][c.charCodeAt(0)-65] = v; this.f.delete(r+c); }
  get(r, c) {
    if (this.f.has(r+c)) {
      let t = 0;
      for (const tok of this.f.get(r+c)) {
        if (tok.includes(':')) {
          const [a, b] = tok.split(':');
          const r1 = +a.slice(1), c1 = a.charCodeAt(0)-65, r2 = +b.slice(1), c2 = b.charCodeAt(0)-65;
          for (let rr = r1; rr <= r2; rr++) for (let cc = c1; cc <= c2; cc++) t += this.get(rr, String.fromCharCode(cc+65));
        } else t += this.get(+tok.slice(1), tok[0]);
      }
      return t;
    }
    return this.g[r][c.charCodeAt(0)-65];
  }
  sum(r, c, refs) { this.f.set(r+c, refs); return this.get(r, c); }
}

class Excel {
    int[][] g; Map> f = new HashMap<>();
    public Excel(int H, char W) { g = new int[H+1][26]; }
    public void set(int r, char c, int v) { g[r][c-'A'] = v; f.remove(r+""+c); }
    public int get(int r, char c) {
        String k = r+""+c;
        if (f.containsKey(k)) {
            int t = 0;
            for (String tok : f.get(k)) {
                if (tok.contains(":")) {
                    String[] p = tok.split(":"); int r1 = Integer.parseInt(p[0].substring(1)), c1 = p[0].charAt(0)-'A';
                    int r2 = Integer.parseInt(p[1].substring(1)), c2 = p[1].charAt(0)-'A';
                    for (int rr = r1; rr <= r2; rr++) for (int cc = c1; cc <= c2; cc++) t += get(rr, (char)(cc+'A'));
                } else t += get(Integer.parseInt(tok.substring(1)), tok.charAt(0));
            }
            return t;
        }
        return g[r][c-'A'];
    }
    public int sum(int r, char c, String[] refs) { f.put(r+""+c, Arrays.asList(refs)); return get(r, c); }
}

class Excel {
    vector> g; map> f;
public:
    Excel(int H, char W) : g(H+1, vector(26)) {}
    void set(int r, char c, int v) { g[r][c-'A'] = v; f.erase(to_string(r) + c); }
    int get(int r, char c) {
        string k = to_string(r) + c;
        if (f.count(k)) {
            int t = 0;
            for (auto& tok : f[k]) {
                if (tok.find(':') != string::npos) {
                    auto p = tok.find(':'); auto a = tok.substr(0, p), b = tok.substr(p+1);
                    int r1 = stoi(a.substr(1)), c1 = a[0]-'A', r2 = stoi(b.substr(1)), c2 = b[0]-'A';
                    for (int rr = r1; rr <= r2; rr++) for (int cc = c1; cc <= c2; cc++) t += get(rr, cc+'A');
                } else t += get(stoi(tok.substr(1)), tok[0]);
            }
            return t;
        }
        return g[r][c-'A'];
    }
    int sum(int r, char c, vector refs) { f[to_string(r) + c] = refs; return get(r, c); }
};

Explanation

This is a mini spreadsheet. Every cell holds either a plain number or a formula that adds up other cells. The trick to keeping it simple is to recompute on read rather than trying to track changes as they happen.

We store the numbers in a grid g and the formulas in a dictionary f keyed by cell. set(r, c, v) drops a number into the grid and deletes any formula on that cell, because a hard-coded value overrides a formula.

sum(r, c, refs) just saves the list of references for that cell into f and then calls get to return the current total. get(r, c) is the heart: if the cell has a formula, it walks each reference. A single ref like A1 adds that one cell; a range like A1:B2 loops over every cell in the rectangle. Each lookup calls get again, so formulas that point at other formulas resolve recursively (a depth-first walk).

Because we never cache, a later set on any referenced cell is automatically reflected the next time you read the formula cell — the value is computed fresh.

Example: after set(1,'A',1) and sum(3,'C',['A1','A1:B2']), asking get(3,'C') adds A1 plus the range covering A1,A2,B1,B2. Later set(2,'B',2) changes the grid, so the next read of C3 recomputes to the new total.

Time: O(refs · grid) Space: O(H·W)