Massive Technical Interviews Tips: Uber Design Excel

http://codeinterviews.com/Uber-Design-Excel/

How would you design an Excel sheet’s Data structure. You need to perform operations like addition. The excel sheet is very sparse and is used to store numbers in the range 1-65K. Index for a cell is known.

class SpreadSheet {  
 private static final int MAX_CELL_INDEX = 65000; 
 private final Map<Integer, Map<Integer, String>> data = new HashMap<>();
 
 public void setValue(int row, int column, String value){  
  checkRowAndColumnIndex(row, column);  
  Map<Integer, String> columnsMap = data.get(row);  
  if( columnsMap == null ){
   columnsMap = new HashMap<>();
   data.put( row, columnsMap );
  }  
  columnsMap.put(column, value);
 }
 
 public String getValue(int row, int column){// change to use Optional  
  checkRowAndColumnIndex(row, column);  
  Map<Integer, String> columnsMap = data.get(row);  
  if( columnsMap != null ){
   return columnsMap.get(column);
  }  
  return null;
 }
}

Follow-up question: In excel, one cell can refer to other cells, if I update one cell, how do you update all the dependent cells？

Follow up 就是涉及到一个cell可能包含其他cell的pointer的时候, 如何获取这个cell的值. 紧接着更新一个cell如何保证所有指向它的cell也能更新.

这个问题可以被转化成经典的Topological sort

http://www.1point3acres.com/bbs/thread-140449-1-1.html

Follow-up question: In excel, one cell can refer to other cells, if I update one cell, how do you update all the dependent cells？若问到存储图片和删除整行整列如何处理。

1，refer大概是比如指A3格子的值受A1格子的影响，简单的比如设定A3=A2+A1等。那么对于每一个cell，加一个list of dependecy，这样更新某个cell的时候，根据它的dependency list做一个bfs来更新相应的所有cell，需要注意的可能是refer loop，比如A1 refer to B2，但是B2 也refer to A1，这个应该可以和面试官讨论应该保留那一个refer link

2，存图片的话应该是存一个image id，然后通过image id从数据库里拿到相应的图片文件信息

3，增删某一行或某一列的话，我能想到的就是对于扫描整个表，对于修改所有收到影响的cell的row和col值

图片最好不要放db里面，放到filesytem，excel存url或者path
http://www.1point3acres.com/bbs/thread-132725-2-1.html
那为了方便column traversal不是还要再加个map<integer, map<integer,cell>>? 加入pointer之后get其实改动只需要check是不是pointer的吧

当时并没有这么做. 根据时间考虑的话, 节省空间更加重要. 而column traversal一般不会扫太多行, 所以当时并没有提出多一个Map. 另外这样维护起来也会容易出bug.

设计一个 Excel ，每个cell里面是一个String。一开始想当然说可以直接用二维矩阵存，后来改成list of lists，最后改成了HashMap。后续还有evaluate一个string相关的问题（给了黑盒evaluate函数，对每个cell实现evaluate和支持修改）。

这个问题可以被转化成经典的Topological sort

excel这题蛮standard
一开始的时候只需要实现insert和get。看网上有很多种解法。比较普遍的是HashMap<Integer, HashMap<Integer, Cell>>. 不过我就直接HashMap<String, Cell>了， String是Cell的名字。比如"A1" -> Cell.
如果输入是行列，就来个leetcode的Excel Sheet Column Number.
然后Cell里存一个integer value，一个fomula，两个ArrayList<String> 一个parents 一个children
存parent和children是为了自身value 或formula变更时可以把dependency的value也change掉
比如如果Cell是一个formula， formula change就必须把parent里的自己摘掉。

其实这个方法有点小白，但是比较容易懂啦--大牛绕道~~

后来问如果存String或图片咋办。String其实就像value 是没有dependency的所以很好办
图片也好办。寸hash完的identifier 图片本身存数据库。

反正到后面我很无赖。不管怎么变我都扯到前面design的value和formula上。。。

Saturday, September 12, 2015

Uber Design Excel

Labels

Popular Posts