找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 15580|回复: 5
收起左侧

跟大家分享一下个人的System Design总结

[复制链接]

4

主题

2

精华

52

积分

资深会员

Rank: 2

积分
52
发表于 10-6-2017 10:07 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 5-13-2016 03:39 PM 编辑

以下是我自己在准备System Design时候做的一些总结,包括了一些常见的题目,名词解释,希望对大家有帮助。


How to design an excel

根据看到的面经,这题会分两个侧重点来问,当然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<Integer, HashMap> 来实现,这样的话我们就只会记录写过data的cell了。

还有一个问题是dependency,因为我们在excel里要实现cell(1,3)=cell(0,0)+cell(0,1)+cell(0,2),所以当cell(0,0)变化的时候,我们要update cell(0,0). 所以每个map需要记录depend他的值(有点像observer pattern里的register,比如说cell(0,0)就要存一个Set,记录所有depend他的Cell (比如Cell(0,1)就要记录Cell(1,3)是他的children,另外要有detection,dependency不能有cycle,这个可以用DFS来做。
另外如果是删除或者添加一整行/列,这个可能就不好做,因为行只要删除对应的那个行就可以,但是列的话只能一个一个删除了。 为了加快速度我们可以让每个cell都记录一下他的上面和下面的列(在插入这个新cell的时候update),这样的话删除的话就我们就只需要删除一个linkedlist了,但是这样的话插入就需要遍历所有的行,需要遍历所有的cell。 如果我们用TreeMap的话,会更快,但是如果修改或者删除的话就是O(logN)而不是O(1)的复杂度了。
还有follow up问题是如果存其他数据,比如说image,甚至audio或者video的话,我们就只存一个url或者是path,等读取的时候我们再从file system或者CDN里面去读取。
如果这个document还放到网上去共享的话,那当user1在修改某个cell的时候,需要给cell加一个锁,可以用mutex来实现,具体就是在edit的时候要调用mutex.aquire(),操作完以后要调用mutex.release();这样可以保证不会有同时的两个人去access同样的data,当然mutex是multithread用的,而不是网上共享用的。 但是同样的道理,我们可以用一个atomic的bit给每个cell来加锁和解锁(比如说这个bit可以放到redis里面的某个key,因为redis是single threaded,所以可以保证所有操作都是atomic的。
Mutex和semaphore的区别,mutex相当于是只有0和1的semaphore,但是要注意一点mutex的加锁和解锁是只能由同一个thread进行的。 而semaphore的加和减是可以由不同thread执行,所以mutex用于加锁而semaphore用于协调几个thread的执行。


Big Data Interview Questions

1、海量日志数据,提取出某日访问百度次数最多的那个IP。
这道题就是用Hash + Heap的办法来做的典型问题。 我们先遍历每个IP,对每个IP算一个Hash,这样每个Hash就均匀的Map到了Hash空间里。 然后根据每个IP计算的Hash(IP)%100 将这个IP放到100个文件中。 这种做法就保证了同一个IP一定会被分到同一个文件中,而且所有IP应该是均匀分布的。 然后对于每个文件里出现IP的频率进行统计(可以用HashMap, 也可以用trie,每个Tire的leaf上存一个freq),然后用MinHeap排序找出每个文件的Top K,然后再合并所有的Top K,就得到了结果。
同样的办法可以用在其他的统计String的TopK频率等等类似的问题中。

2. 海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。
如果每个数据只出现在同一台电脑上,那么就可以用上面的方法解决,还省去了Hash的过程。 但是如果同样的数据可能出现在不同的电脑中呢?
那么我们就要把相同的数据用Hash的办法放到同样的电脑中。 相当于重新分布一下。
或者我们直接用另外一台电脑统计所有电脑中数据出现的次数(因为有重复,所以有可能一台电脑就可以放的下),然后再按频率进行排序。
同样的问题还可以用一些分布式的framework来做比如map reduce。 把每个document分给mapper,mapper遍历所有的word,然后做成word->1这样的pair,然后经过shuffle以后变成word->{1,1,1,1..}这样的,然后我们只要在reducer里面分析这个组合就可以了。

3. 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?
同样的对每个url进行Hash,然后根据Hash(url)的结果将他们分成1000份(这样每一份是0.32G,如果hash算法好的话)。 然后a 和b的每个相对应的file进行比较看看有没有重复的(用hashmap就可以)因为如果是同样的hash算法的话,相同的url一定是分配到相同的file中的。
或者我们也可以给其中一个url生成一个bloom filter,然后用这个bloom filter来filter另外一个hash,如果没有重复,那么我们可以肯定没有重复,如果bloom filter的结果说可能有重复,那么我们再进到array里一个一个检查。


4. 2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。
其实我们只需要把所有整数划分到能够放进内存里的bucket里面,比如说2^26 32M大小的file,然后每次check这个范围内的整数,用bitmap来看是否有重复的。 给每个integer assign一个bit,如果出现过就把这个bit设置成1,这样就知道这个bit是否见过了
给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
同样只要用bitmap,每个bit assign一个数,只要那个对应的数被设置成1了,就表示那个数存在,是逻辑和算法上的,和计算机的物理特性没有关系。
外排序,外排序

5. 有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16个字节,内存限制大小是1M。 返回频数最高的100个词。
所以我们可以用内存作为缓冲区来进行外排序,将所有的词都按String比较大小的方法外排序。 这样所有的string都已经排好序了,然后我们再一个一个统计所有string出现的次数,最后输出频率最高的那个。

Web Service

Failure rate = number of users who failed to use the service/total user who used the service.

How to collect the data for failure rate? User send a log to server when it visited our website
What happened wen you enter http://www.google.com in your browser and hit enter.
first go to DNS and get the IP address of http://www.google.com
DNS lookup and prepare reply
DNS send reply back.
send request to the webserver.
prepare webpage reply.
send web page reply.
Process webpage.
request player
request file

Failure analysis:
DNS failure :
WebServer failure: Reverse Proxy (add more servers). Reduce the size of webpage (Simplify content, Rewrite JS code). Compress/merge images. Lazy Load, batch connection
More Cacheable pages. Change dynamic webpage into static webpage.
Limit request

Process File download
1. send request to the file server
2. Network error (file server failure?),
3. fail to establish connect,
4. fail to find file,
5. Network error when responding.

CDN:
Distributed File server.address is provided by the web server, no need to go to the DNS.

评分

参与人数 1金钱 +6 收起 理由
Sophia + 6 感谢您的认真和用心的分享!大米满满送上!

查看全部评分

0

主题

0

精华

2

积分

新米人

Rank: 1

积分
2
发表于 10-6-2017 11:37 AM | 显示全部楼层
感谢lewis000000分享~~~
回复 支持 反对

使用道具 举报

发表于 10-6-2017 11:39 AM | 显示全部楼层
感谢您的认真和用心的分享!大米满满送上!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表