优步系统设计 | Hello World

优步系统设计 | Hello World

根据看到的面经，这题会分两个侧重点来问，当然get和set是最基本的， 1， 重点要处理各个cell之间的dependency，比如cell(1,3)是用公式算出来的cell(1,3)=cell(0,0)+cell(0,1)+cell(0,2)，我会用两层哈希表表示整个表格(unordered_map> workbook)，然后每个Cell中保存一个unordered_set parents；(所有计算当前Cell需要依赖的cells，上例就是cell(0,0)，cell(0,1)和cell(0,2)) 和 unordered_set children; (所有依赖这个Cell通过公式计算出来的cells)，每次改变cell的值就要对children和parents做相应的改变； 2， 重点是要处理add或delete一整行或一整列，我会用2d数组，vector> workbook, add的话就直接append，delete行的话就直接erase对应的行，delete列的话就根据列下标，对每行进行erase，好写，但是效率有点低，如果大家有更好的想法，可以一起讨论下。 首先这的想法可能是用一个2darray，但是我们我们不知道初始的大小，所以我们可以用list of list，这样的话还是会要用到多余的空间。即使这些空间没有存数据。所以最好的办法是用HashMap 来实现，这样的话我们就只会记录写过data的cell了。 还有一个问题是dependency，因为我们在excel里要实现cell(1,3)=cell(0,0)+cell(0,1)+cell(0,2)，所以当cell（0，0) 变化的时候，我们要update cell(0,0).

Read full article from 优步系统设计 | Hello World