Design Excel Sum Formula

This page explains Java solution to problem Design Excel Sum Formula using HashMap data structure.

Problem Statement

Your task is to design the basic function of Excel and implement the function of sum formula. Specifically, you need to implement the following functions:

• Excel(int H, char W): This is the constructor. The inputs represents the height and width of the Excel form. H is a positive integer, range from 1 to 26. It represents the height. W is a character range from A to Z. It represents that the width is the number of characters from A to W. The Excel form content is represented by a height * width 2D integer array C, it should be initialized to zero. You should assume that the first row of C starts from 1, and the first column of C starts from A.
• void Set(int row, char column, int val): Change the value at C(row, column) to be val.
• int Get(int row, char column): Return the value at C(row, column).

• int Sum(int row, char column, List of Strings : numbers): This function calculate and set the value at C(row, column), where the value should be the sum of cells represented by numbers. This function return the sum result at C(row, column). This sum formula should exist until this cell is overlapped by another value or another sum formula.

  numbers is a list of strings that each string represent a cell or a range of cells. If the string represent a single cell, then it has the following format : ColRow. For example, "F7" represents the cell at (7, F).

  If the string represent a range of cells, then it has the following format : ColRow1:ColRow2. The range will always be a rectangle, and ColRow1 represent the position of the top-left cell, and ColRow2 represents the position of the bottom-right cell.

Input:
Excel(3,"C");
construct a 3 * 3 2D array with all zero.
  A B C
1 0 0 0
2 0 0 0
3 0 0 0

Set(1, "A", 2);
set C(1,"A") to be 2.
  A B C
1 2 0 0
2 0 0 0
3 0 0 0

Sum(3, "C", ["A1", "A1:B2"]);
set C(3,"C") to be the sum of value at C(1,"A") and the values sum of the rectangle range whose top-left cell is C(1,"A") and bottom-right cell is C(2,"B"). Return 4.
  A B C
1 2 0 0
2 0 0 0
3 0 0 4

Solution

package com.vc.hard;

import java.util.*;

class DesignExcelSumFormula {

    private Cell[][] excel;

    class Cell {
        //A Cell can have a value
        int val = 0;

        //Or Cell can have formula
        //key  : Cell Reference
        //value: How many times Cell Reference has occurred in formula
        HashMap<Cell, Integer> sumFormulaMap = new HashMap<>();

        //Assigns
        Cell(int val) {
            setValue(val);
        }

        //Converts String Formula to Cell Reference
        Cell(String[] formula) {
            setFormula(formula);
        }


        public void setValue(int val) {
            sumFormulaMap.clear();
            this.val = val;
        }

        //Converts String Formula to Cell Reference
        public void setFormula(String[] formulas) {
            sumFormulaMap.clear();
            for(String formula: formulas) {
                int index = formula.indexOf(":");
                if(index < 0) {
                    int[] pos = getPos(formula);
                    int row = pos[0];
                    int col = pos[1];
                    if(excel[row][col] == null) {
                        excel[row][col] = new Cell(0);
                    }
                    sumFormulaMap.put(excel[row][col], sumFormulaMap.getOrDefault(excel[row][col], 0) + 1);
                }
                else {
                    String[] range = formula.split(":");
                    int[] from = getPos(range[0]);
                    int[] to = getPos(range[1]);
                    for(int row = from[0]; row <= to[0]; row++) {
                        for(int col = from[1]; col <= to[1]; col++) {
                            if(excel[row][col] == null) {
                                excel[row][col] = new Cell(0);
                            }
                            sumFormulaMap.put(excel[row][col],
                                    sumFormulaMap.getOrDefault(excel[row][col], 0) + 1);
                        }
                    }
                }
            }
        }

        public int getValue() {
            if(sumFormulaMap.size() == 0) return val;
            else {
                int sum = 0;
                for(Map.Entry<Cell, Integer> entry: sumFormulaMap.entrySet()) {
                    int cellValue = entry.getKey().getValue();
                    int ocurrance = entry.getValue();
                    sum += cellValue * ocurrance;
                }
                return sum;
            }
        }

        private int[] getPos(String formula) {
            int col = formula.charAt(0) - 'A';
            int row = Integer.parseInt(formula.substring(1));
            return new int[]{row, col};
        }
    }


    public DesignExcelSumFormula(int H, char W) {
        this.excel = new Cell[H + 1][W - 'A' + 1];
    }

    public void set(int r, char c, int v) {
        if(excel[r][c - 'A'] == null) excel[r][c - 'A'] = new Cell(v);
        else excel[r][c - 'A'].setValue(v);
    }

    public int get(int r, char c) {
        if(excel[r][c - 'A'] == null) return 0;
        else return excel[r][c - 'A'].getValue();
    }

    public int sum(int r, char c, String[] strs) {
        if(excel[r][c - 'A'] == null) excel[r][c - 'A'] = new Cell(strs);
        else excel[r][c - 'A'].setFormula(strs);
        return excel[r][c - 'A'].getValue();
    }
}

/**
 * Your Excel object will be instantiated and called as such:
 * Excel obj = new Excel(H, W);
 * obj.set(r,c,v);
 * int param_2 = obj.get(r,c);
 * int param_3 = obj.sum(r,c,strs);
 */

Time Complexity

Set(int row, char column, int val) takes O(1)
Get(int row, char column) takes O(N)
int Sum(int row, char column, List of Strings : numbers) takes O(L)
Where N is total number Cell references we have in a formula
L is length of input list which has formulas

Space Complexity

O(H, W) Where
H is number of rows in an excel
W is number of cols in an excel