https://leetcode.com/discuss/interview-question/315303/Uber-phone-screen-Design-Spreadsheet

excel design

  static interface Excel {
    void put(String cell, Integer value, String formula);
    int get(String cell);
  }

  static class CellNode {
    String cell;
    String formula;
    int value;

    public CellNode(String c, String f){
      cell = c;
      formula = f;
    }

    public CellNode(String c, int v) {
      cell = c;
      value = v;
    }
  }

  static class ExcelImpl implements Excel {
    Map<String, Set<String>> graph;
    Map<String, CellNode> nodes;

    Map<String, Integer> result;

    public ExcelImpl() {
      graph = new HashMap<>();
      nodes = new HashMap<>();
    }

    public void put(final String cell, final Integer value, final String formula) {
      CellNode node = null;
      if(formula == null)
        node = new CellNode(cell, value);
      else
        node = new CellNode(cell, formula);

      nodes.put(cell, node);

      if(!graph.containsKey(cell)) {
        graph.put(cell, new HashSet<>());
      }

      if(formula != null) {
        StringTokenizer st = new StringTokenizer(formula, "*+");
        while(st.hasMoreTokens()) {
          graph.get(cell).add(st.nextToken());
        }
      }
    }

    public int get(final String cell) {
      if(nodes.get(cell)==null)
        return -1;

      if(nodes.get(cell).formula == null)
        return nodes.get(cell).value;
       
      result = new HashMap<>();
      calculateRec(cell);

      return result.get(cell).intValue();
    }

      // the dependencies among the cells form a tree, here we 
    // go down the tree via DFS recursion to compute the value for each cell/node
    // result map store the result of each cell's computed value
    private int calculateRec(final String cell) {
      if(result.containsKey(cell))
        return result.get(cell);

      if(nodes.get(cell) == null) //assume the formula is always valid, then this likely a computed value
        return Integer.valueOf(cell);

      if(nodes.get(cell).formula == null) {
        result.put(cell, nodes.get(cell).value);
        return nodes.get(cell).value;
      }

      String formula = nodes.get(cell).formula;

      Stack<String> operands = new Stack<>();
      Stack<Character> operators = new Stack<>();

      this.parseFormula(formula, operands, operators);

      while(!operators.isEmpty()) {
        char operator = operators.pop();
        String cell1 = operands.pop();
        String cell2 = operands.pop();

        if(operator == '+') {
          char next = ' ';
          if(!operators.isEmpty())
            next = operators.peek();

          if(next == '*') {
            operators.pop();
            String cell3 = operands.pop();
            operands.push(String.valueOf(calculateRec(cell3) * calculateRec(cell2)));

            //put it back
            operators.push(operator);
            operands.push(cell1);
          }else{
            operands.push(String.valueOf(calculateRec(cell1) + calculateRec(cell2)));
          }
        }else{
          operands.push(String.valueOf(calculateRec(cell1) * calculateRec(cell2)));
        }
      }

      int re = Integer.valueOf(operands.pop());
      result.put(cell, re);
      return re;
    }

    private void parseFormula(final String formula, final Stack<String> operands, final Stack<Character> operators) {
      Stack<Character> tempC = new Stack<>();
      Stack<String> tempS = new Stack<>();

      int i = 0, len = formula.length();
      while(i<len) {
        char c = formula.charAt(i);
        if(c == '+' || c == '*') {
          tempC.push(c);
        }else{
          StringBuilder sb = new StringBuilder();
          sb.append(c);
          while(i+1<len && formula.charAt(i+1)!='+' && formula.charAt(i+1)!='*'){
            sb.append(formula.charAt(i+1));
            i++;
          }
          tempS.push(sb.toString());
        }
        i++;
      }

      while(!tempC.isEmpty())
        operators.push(tempC.pop());

      while(!tempS.isEmpty())
        operands.push(tempS.pop());

    }

  }

public static void main(final String[] args) {
    ExcelImpl excel = new ExcelImpl();
    excel.put("A1", 1, null);
    excel.put("A2", 2, null);
    excel.put("B1", null, "A1+A2+A2");
    System.out.println(excel.get("B1"));

  }