https://drive.google.com/file/d/0B6RF3dJtuOBnbnFEWERXVHN1OWs/view
LinkedInSystem Design
1. 已知一个函数，输入用户ID，可以返回该用户的所有好友(degree 1 friends)，并且能够实现按照好友ID从小到大排序。现要求实现算法和相关的系统，返回一个用户的所有好友的好友(degree 2 friends), 以及degree 3 friends。
Note: 通过临时加一些限制条件，能够进行时间或空间的优化。
2. 已知一个文件系统，可以create files, delete files, sequentially scan file content, read file content randomly, append file content.对于key-value pairs，在给定的文件系统中实现put，get，delete 方法。其中key比较小，全部key可以放在内存中，value会比较大。
Answer:
a. In the main memory, maintain a hashmap, key is the given input key, value is thefile ptr and line ptr(key-value pair location in the file system).
b. Each time we need to update the value, write a new key value pair at the end of the file, and also update the related key value pairs in the main memory. Then when main memory cracks, we can reconstruct the main memory hashmap from the files content.
c. Merge:
Make file modifications to save space: scan the file sequentially for each key to find the latest update, then put the latest key-value pairs into another file. After we finished doing this for all the keys in a file, delete that file.
d. Deal with synchronization: when we do the file modification, put all the newest updates into another file, then replay it.
e. Each file should have a limited amount of different keys, so that file modification is not that hard.
3. Design Tiny URL/ Note: 如何配置Memcache。
4. Design LinkedIn
a. Search功能里inverted index 和data of user , data of company 怎么存，分别用NoSQL还是SQL?-> 列举了NoSQL和SQL区别，最后选择SQL。
b. 前端模块的service/ application区别。
c. 设计timeline，push / pull model。
5. How to design LinkedIn profile page which can support rich media such as vide0, picture and audio?
6. LinkedIn有很多host server在做很多不同的service，这些service发出的exception都会被写到log里。设计一个系统，监测24小时之内top 500的exceptions。
7. How to design the API for searching similar people?
Details about the frontend / backend.
8. Design a system tocal culate the revenues generated by ad click.
9. 设计系统来实现5分钟，1小时，24小时内分享前10多的文章/ Note:Distributed System
10. 社交网站上的文章转发，如何设计系统可以得到实时的转发量榜单和weekly digest，要求数据库的设计。有人转发一个文章时request是什么样的，如何快速得到实时的转发量榜单，如何得到weekly digest等。Note:
a. weekly digest就把每转发一次的信息存入到数据库中，然后直接读取就行了。
b. 实时转发我说可以保存到一个in-memory database里面，可以快速读取。
11. Design IP Black List
这个考虑起来很有意思，先要问问是IPv4还是IPv6. 前者所有地址加起来共有2^32个，如果内存足够大，一个BITMAP在O(1)就搞定了。如果内存不够或者是IPv6，那就考虑分块，多级索引，二分查找，反正复杂度立刻上升为是O(LOG)，当然可以详细讨论这个LOG具体怎么做。
12. Design a recommendation system
Data collection / Training algorithm / Evaluate recommendation results / Evolve with C
13. 假设现在我们有N个服务器，每个服务器有一个check sum，如果黑客攻击其中某一个服务器，那么该服务器的check sum就会改变，一旦改变，就是被黑客攻击了。设计一个系统，如何detect hacker attack。
14. 设计Amazon Buy页面
a. 如何设计database来存信息，然后render page? 用SQL来存各个table。
b. 如果数据很大怎么办?
可以把shared data存在各个slave上，靠master去query，然后OOD server interface，怎样读取各个table的信息，然后写了一个server class来用这些interface来render page。
c. 如果很多客户同时读怎么办，我的解决方法有cache / multi-threading。
d. How to suggest product，建一个Product weighted graph, 然后用BFS。
15. Design a dashboard system for administrator to monitor the top URL in last 5 minutes.
Note: high traffic, database schema design, user experience, performance issue, communication protocol, etc.
16. Design a notebook application like evernote or onenote, it should support search and collaboration operations.
17. 一个user enter company or university information while signing on, how to help the user better locate his company / university?
我先说用hashtable存company / university 和id pairs，然后用Trie实现auto-completion帮助user完成look-up。如果High-level怎么快速locate？可以combine location, rank of the top selected company / university, connection’s company / university, logo来推荐。如果用户填资料的时候没有选对应的选项，自己填了一个怎么办？可以暂时存null，之后再让用户complete information。
http://systemdesigns.blogspot.com/2015/12/blog-post_7.html
另一方面是，其实大家也都没设计经验 基本就算会也是自学的 凭借这个不敢保证能找到最聪明的，但是至少能找到勤奋好学的人 至于设计本身 我觉得BFS比DFS重要 就是知道的要广 能设计出大体框架 之后关键地方来dfs 把细节吸收 就足够了 真心觉得 对咱们的设计的要求 不会太高太高。
面经上很多人挂了设计 其实我觉得可能他们真没有怎么认真准备 一知半解就杀上去了 要是按照咱们这个小组这么玩下去 估计有个一个月 设计完全不成问题！我保证咱们肯定比一般的面试官知道的还多还全还细！真心的。系统群现在的已有资
按照面试的level 也不是什么竞赛 没那么难 所以要的是熟练 理解深刻。想达到这些 那就像练习三分球一样 反复练习。就是反复刷 提高熟练度。
2. 系统。
是考察对CS知识储备，所以要多看 多学 知道的越多越好。知识储备多了 自然面试的时候白话的底气就充足了。要不面试官问 数据咋搜索 尼玛只会挨个遍历 那不是必然挂。但是所谓各种知识基本就是看了就会 不看一辈子都不会 所以要多看。
这种设计面试 问两个问题 就看出知识掌握的level了。说到底 算法和设计 都是砸时间 一个多练 一个多看。
http://www.jiuzhang.com/qa/194/
http://chen-tam.github.io/2016/04/09/note_system_design_question/
http://www.duweiwen.com/wechat/337755882288ee.html
你可以提问、在白板上画示意图，甚至可以激发出面官的想法。这道问题的限制条件是什么？系统设计时需要什么输入
http://www.wzaobao.com/p/j2fBlt.html
2) design
解这种题是个*交流*的过程，或者说是给出方案然后获取反馈的不断循环的过程。
一般的流程：
首先你要问清楚requirement；
然后可以讲一下high level architecture，就是分成哪几个component，互相之间如果
interact，在白板上画一画；
之后面试官可能会让你深入某个component detail讨论；
也有可能变换requirement让你重新设计
另外，f家还喜欢让你估算机器之类的，做一些back-of-envelopme calculation。所以
最好对一些计算机相关的基本常数，fb的用户量等等有个大概的了解。
准备的时候建议看看fb的design高频题。一方面有可能面试的时候刚好碰到这几个
topic，另一方面其实很多design都是相通的。
http://geekband.com/course/1029
二.系统设计中七剑客
7.同步
8.网络
9.数据库
10.分布式
11.性能
12.估算
13.面向对象
14.案例
· 设计网站信息流设计
· 日志统计
· 产品页面设计
三.搭建大规模可扩展的系统
15.分布式系统
16.数据库系统
17.经典架构 (master/slave)
18.设计原则：CAP理论
19.一致性介绍
20.关系型数据库
21.ACID vs. BASE
22.sharding分片
23.一致性hash
24.NoSQL数据库
25.Cassandra
26.实时系统：Kafka, Storm
27.案例：
· 电商网站设计
· 网页爬虫设计
四.大数据系统
28.大数据基础：Hadoop，Spark入门
29.教你如何看懂MapReduce，BigTable，GFS三篇paper
30.聊天系统设计
31.估算机器
32.其他常见面试中的设计题目
LinkedInSystem Design
1. 已知一个函数，输入用户ID，可以返回该用户的所有好友(degree 1 friends)，并且能够实现按照好友ID从小到大排序。现要求实现算法和相关的系统，返回一个用户的所有好友的好友(degree 2 friends), 以及degree 3 friends。
Note: 通过临时加一些限制条件，能够进行时间或空间的优化。
2. 已知一个文件系统，可以create files, delete files, sequentially scan file content, read file content randomly, append file content.对于key-value pairs，在给定的文件系统中实现put，get，delete 方法。其中key比较小，全部key可以放在内存中，value会比较大。
Answer:
a. In the main memory, maintain a hashmap, key is the given input key, value is thefile ptr and line ptr(key-value pair location in the file system).
b. Each time we need to update the value, write a new key value pair at the end of the file, and also update the related key value pairs in the main memory. Then when main memory cracks, we can reconstruct the main memory hashmap from the files content.
c. Merge:
Make file modifications to save space: scan the file sequentially for each key to find the latest update, then put the latest key-value pairs into another file. After we finished doing this for all the keys in a file, delete that file.
d. Deal with synchronization: when we do the file modification, put all the newest updates into another file, then replay it.
e. Each file should have a limited amount of different keys, so that file modification is not that hard.
3. Design Tiny URL/ Note: 如何配置Memcache。
4. Design LinkedIn
a. Search功能里inverted index 和data of user , data of company 怎么存，分别用NoSQL还是SQL?-> 列举了NoSQL和SQL区别，最后选择SQL。
b. 前端模块的service/ application区别。
c. 设计timeline，push / pull model。
5. How to design LinkedIn profile page which can support rich media such as vide0, picture and audio?
6. LinkedIn有很多host server在做很多不同的service，这些service发出的exception都会被写到log里。设计一个系统，监测24小时之内top 500的exceptions。
7. How to design the API for searching similar people?
Details about the frontend / backend.
8. Design a system tocal culate the revenues generated by ad click.
9. 设计系统来实现5分钟，1小时，24小时内分享前10多的文章/ Note:Distributed System
10. 社交网站上的文章转发，如何设计系统可以得到实时的转发量榜单和weekly digest，要求数据库的设计。有人转发一个文章时request是什么样的，如何快速得到实时的转发量榜单，如何得到weekly digest等。Note:
a. weekly digest就把每转发一次的信息存入到数据库中，然后直接读取就行了。
b. 实时转发我说可以保存到一个in-memory database里面，可以快速读取。
11. Design IP Black List
这个考虑起来很有意思，先要问问是IPv4还是IPv6. 前者所有地址加起来共有2^32个，如果内存足够大，一个BITMAP在O(1)就搞定了。如果内存不够或者是IPv6，那就考虑分块，多级索引，二分查找，反正复杂度立刻上升为是O(LOG)，当然可以详细讨论这个LOG具体怎么做。
12. Design a recommendation system
Data collection / Training algorithm / Evaluate recommendation results / Evolve with C
13. 假设现在我们有N个服务器，每个服务器有一个check sum，如果黑客攻击其中某一个服务器，那么该服务器的check sum就会改变，一旦改变，就是被黑客攻击了。设计一个系统，如何detect hacker attack。
14. 设计Amazon Buy页面
a. 如何设计database来存信息，然后render page? 用SQL来存各个table。
b. 如果数据很大怎么办?
可以把shared data存在各个slave上，靠master去query，然后OOD server interface，怎样读取各个table的信息，然后写了一个server class来用这些interface来render page。
c. 如果很多客户同时读怎么办，我的解决方法有cache / multi-threading。
d. How to suggest product，建一个Product weighted graph, 然后用BFS。
15. Design a dashboard system for administrator to monitor the top URL in last 5 minutes.
Note: high traffic, database schema design, user experience, performance issue, communication protocol, etc.
16. Design a notebook application like evernote or onenote, it should support search and collaboration operations.
17. 一个user enter company or university information while signing on, how to help the user better locate his company / university?
我先说用hashtable存company / university 和id pairs，然后用Trie实现auto-completion帮助user完成look-up。如果High-level怎么快速locate？可以combine location, rank of the top selected company / university, connection’s company / university, logo来推荐。如果用户填资料的时候没有选对应的选项，自己填了一个怎么办？可以暂时存null，之后再让用户complete information。
http://systemdesigns.blogspot.com/2015/12/blog-post_7.html
Q: 为什么面试new grad会考设计呢？
一方面是，应对现在IT的情况 要提高面试bar 事实证明 提高算法没任何用处 所以就这么搞了。另一方面是，其实大家也都没设计经验 基本就算会也是自学的 凭借这个不敢保证能找到最聪明的，但是至少能找到勤奋好学的人 至于设计本身 我觉得BFS比DFS重要 就是知道的要广 能设计出大体框架 之后关键地方来dfs 把细节吸收 就足够了 真心觉得 对咱们的设计的要求 不会太高太高。
面经上很多人挂了设计 其实我觉得可能他们真没有怎么认真准备 一知半解就杀上去了 要是按照咱们这个小组这么玩下去 估计有个一个月 设计完全不成问题！我保证咱们肯定比一般的面试官知道的还多还全还细！真心的。系统群现在的已有资
按照面试的level 也不是什么竞赛 没那么难 所以要的是熟练 理解深刻。想达到这些 那就像练习三分球一样 反复练习。就是反复刷 提高熟练度。
2. 系统。
是考察对CS知识储备，所以要多看 多学 知道的越多越好。知识储备多了 自然面试的时候白话的底气就充足了。要不面试官问 数据咋搜索 尼玛只会挨个遍历 那不是必然挂。但是所谓各种知识基本就是看了就会 不看一辈子都不会 所以要多看。
这种设计面试 问两个问题 就看出知识掌握的level了。说到底 算法和设计 都是砸时间 一个多练 一个多看。
http://www.jiuzhang.com/qa/194/
系统设计面试的传统来自于Google、Facebook、Alibaba、Baidu等互联网公司，它们面对的是每天亿级别的用户量以及上T甚至P级别的数据量，这时候性能总会成为瓶颈，而性能分析的起点往往是QPS。对于此类大规模用户量的系统，系统“分布式”架构的设计往往会决定着性能。
但是对于一些其它的场景，比如“编译器”和“驱动开发”，它们和底层更加结合，往往更需要操作系统方面的知识和设计理念（此时的分布式被弱化了）。对于前端场景来说，如果只是关注View这一层，也不会太关心分布式性能，这往往由后端工程师来设计和解决。但是即使对于前端，也已经越来越和后端结合，因此有了全栈工程师的趋势，他们考虑的会更多，从数据、后端、前端整个角度来进行系统的设计和研发。
再举个今天我刚刚碰到的例子，我上午在用Meteor+React开发，但是首页加载较慢。如何才能提升呢？于是我在Browser端加入了数据库的缓存来优化性能。因此，我们在第四节课会从web的角度来理解性能，第七节课也会介绍OOD的设计，这些都是系统设计的一部分。
但是即便如此，我们已经讲过的很多理念依然适用于这些“特定”场景的研发，例如JS的V8引擎的性能优化。
当然，我们可以说如果日活跃用户量在1K以内，或者QPS在10以内的系统不需要过于关注性能。或者说当一个模块已经被其他人设计好之后，我们也可以不用太关注这些。
但是，对于有志于攀登cs高峰的我们，对于“分布式”越来越融入生活的点点滴滴，面对着百万级千万级的用户，也许“系统的”掌握系统设计还是必要的，而且面试也会考呀。
至于你问题的另一个问题，做后端必然需要系统设计，但是其他岗位也需要呀，比如数据分析，比如平台架构，比如我刚才提到的前端：）不过我之前面iOS工程师的时候却是没有问他分布式系统设计的问题……
面向对象，接口设计，设计模式，数据库表，分布式
关于高并发系统设计。主要有以下几个关键技术点：缓存，索引，数据分片，锁粒度尽可能小。
常见分布式系统设计问题
如何设计Twitter，短网址系统设计，如何设计Uber
分布式系统
1)Inverted index
2)Anagram
3) Word Count
4) Distributed File System Design 设计
实时位置系统
1) Design Yelp
2) Design Uber
3) Design Whatsapp
搜索系统设计
1) crawler
2) typeahead
3) inverted index
failure rate, DNS, web server, file server, timeout, content delivery network, cookie, HTTP, divide and conquer, Internet service provider, hosts, hijack, retention rate, cache, lazy load, rate limiter, QPS, counter , expire, request list, token bucket
网站系统设计
1) What happend if you visit www.google.com?
2）How to design rate limiter?
3) How to design data log?
面向对象设计
数据库系统设计
database, primary/foreign key, table, row, attribute, index, transaction, log, lock, lifecycle graph, binary search tree, B+Tree, atomicity, consistency, isolation, durability, session
分布式系统
1)Inverted index
2)Anagram
3) Word Count
4) Distributed File System Design 设计
实时位置系统
1) Design Yelp
2) Design Uber
3) Design Whatsapp
搜索系统设计
1) crawler
2) typeahead
3) inverted index
failure rate, DNS, web server, file server, timeout, content delivery network, cookie, HTTP, divide and conquer, Internet service provider, hosts, hijack, retention rate, cache, lazy load, rate limiter, QPS, counter , expire, request list, token bucket
网站系统设计
1) What happend if you visit www.google.com?
2）How to design rate limiter?
3) How to design data log?
面向对象设计
数据库系统设计
database, primary/foreign key, table, row, attribute, index, transaction, log, lock, lifecycle graph, binary search tree, B+Tree, atomicity, consistency, isolation, durability, session
- 设计一个牌类游戏 OOD
- 设计一个服务监视系統。说你有一堆服务器和一堆服务，怎么监视服务状态。 系统设计。各种情况。各种要求。
- 设计一个企业内部用的那种日志系统。大概的用途是A发现一个什么问题，log问题，相关的人会接到通知。半系统半OOD。中间面试我的人想给我点提醒。说中间某部分可以用某种design pattern来做。不过那个design pattern不是factory singleton observer strategy等几个常见的。所以提示了和没提示一样。
- 设计一个和配置相关的系统。大概的功能是比如A要买你的软件，人家可能不需要把你所有的功能买走。他提出了一些他想实现的功能，然后你把你内部的一些模块啥的拼一拼然后给人家。这样一个系统怎么设计。
- 要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。（题目还给出了一系列的数据，比如：站点数总共为5000万，IP地址有1000万，等等）
- 有N台机器，M个文件，文件可以以任意方式存放到任意机器上，文件可任意分割成若干块。假设这N台机器的宕机率小于1/3，想在宕机时可以从其他未宕机的机器中完整导出这M个文件，求最好的存放与分割策略。
- 假设有三十台服务器，每个上面都存有上百亿条数据（有可能重复），如何找出这三十台机器中，根据某关键字，重复出现次数最多的前100条？要求用Hadoop来做。
- 设计一个系统，要求写速度尽可能高，说明设计原理。
- 设计一个高并发系统，说明架构和关键技术要点。
- 有25T的log(query->queryinfo)，log在不段的增长，设计一个方案，给出一个query能快速反回queryinfo
一些其他题目
- 设计文件系统
- 数据结构for spreadsheet
- 一个app需要用cache，怎么实现thread safe
- social network, billions id, every id has about 100 friends roughly, what is
max connections between any two ppls. write algorithm to return min
connections between two ids: int min_connection(id1, id2)
you can call following functions
expand(id) return friends list of id
expandall(list) return friends union of all the ids in the list
intersection(list1, list2) return intersection
removeintersection(list1, list2) - Open google.com, you type some words in the edit box to search something, it will return lots of search results. Among these returning results (that
is, website link), you may only CLICK some results that are interesting to you. The system will record the “CLICK”action. Finally, you will have the search results (i.e. url) and “CLICK” informatin at hand.
Question: how do you find the similarity of these searching? - 如何找出最热门的话题(根据tweets)。如果一个话题一直热门，我们不想考虑怎么办
- Discuss design challenges of a distributed web crawler running on commercial PCs. How to utilize network bandwidth of those PCs efficiently?
- Design a site similar to tinyurl.com
- large log file,含有 customer id, product id, time stamp想得到在某一天中某个custom看网页的次数1. 足够memory 2. limited memory
- 设计一个actor和movie的数据库的schema, 支持从movie得到它的actors和从actor得到ta出现过的moive (Google, phone, 2006)
- 某建筑有五十层高,打算装俩电梯,设计该电梯系统
- how to design facebook’s newsfeed?
- 一个文件里n行m列，每行是一个record，每列一个feature，你时不时要按不同feature排序和查找。不能用数据库，文件大小内存能装下，数据结构和算法不限，语言不限，给出你最好的办法。
- Design online game
- static 变量用来在整个class中共享数据.基于此，各种synchronization技术， 以及busy waiting的优缺点，啥时候要用基于busy waiting的 spinlock主要是基于性能的探讨。 如果有一个应用程序运行时没有达到timing constraint，
你如何去分析问题出在哪儿， 可以用什么工具或者技术。 - 设计题， 有一个多台机器构成的cluster。 现在有大量公司的数据文件 （并有多个备份）。 如果设计一个算法，使得每台机器尽量均衡的使用，并且 每个公司文件的不同copy不能存在于同一台机器上。主要的Idea就是用round-robin的方式assign每个公司的原数据文件到一台机器，再结合使用hashtable。
Interviewer提到我的解法正是他现在在使用的解法。 - Design a class providing lock function which provide lock only if it sees there are no possible deadlocks.
- 设计一个分布式文件系统，给定path name，可以读写文件。具体的system design这里就不提了。其中一个细节是，给定path name，怎么知道哪个node拥有这个文件。我提出需要实现一个lookup function，它可以是一个hash function，也可以是一个lookup
table。如果是lookup table，为了让所有client sync，可以考虑额外做一个lookup cluster。然后Interviewer很纠结，既然可以用hash function，为什么还搞得那么复杂。我就告诉他hash function的缺点。假定一开始有N个node，hash function把M个文件uniformly distribute到N个node上。某天发现capacity不够，加了一个node。首先，要通知所有的client machine，configuration 改变了。如果不想重启client
machine的process，这不是一个trivial job。其次，文件到node的mapping也变了。比如，本来按照hash function，一个文件是放在node 1。加了一个node 后，它可能就map到node 2了。平均来说，N/(N
+1)的文件需要move到新的node。这个data migration还是很大的。然后我就提出一些hash function的design，可以减少data migration。最后他提了一个问题，说要实现一个function，要统计distributed file system所有目录的大小。前提是，一个目录下的文件可能放在不同的node上。我说这个不就是在每个node上统计，然后发到一个merge吗。他说对，但是又问用什么data
structure来表示。我说这就是hash table，key就是directory name，value就是大小。因为directory本身是树结构，这个hash table的key可以用tree来组织。最后让我实现一个function，把我说得这个data structure serialize成byte array。因为这个byte array就是网络传输的data。我用了depth first traverse。不过等我程序写完，才发现，用breath first traverse会更方便，code也会很简洁 - 超大图的存储问题
- 给个Lock w/ two atomic method lock() and unlock()，请用lock实现一个文件读写的系统，要求：
- reader blocks writer;
- writer blocks reader;
- writer blocks writer;
21。设计一个web cache server，假设存储网页数量是10个billion，打算怎么设计
22.你可以得到网站访问记录，每条记录有user IP, 写一个程序，要随时能算出过去5分钟内访问次数最多的1000个IP. 这个好像跟着这个rolling window 的precision 有关，所以我们暂且定为5秒钟update 一次window
- Design free and malloc.
- how to design data structures for a facebook network and how to design an algorithm to find connection? How to optimize it if data is distributed
into multiple computers? - design a deck class and member function to randomly select a card from those cards which haven’t been selected before. (You can assume the number
of this function call will never be larger than the number of cards) For example, we have a deck of four card: 1,2,3,4. First it may select 3, then next time it should randomly select one from 1,2,4… And design a member function to reset. - google search design problem. How to distribute data and how to design backup system
- 设计一个online chat system
- design bit.ly url shortening web service。算法设计，后端存储，中间层cache，前端load balance，最后是web analytics。
- Design and implement an algorithm that would correct typos: for example, if an extra letter is added, what would you do?
- Suppose there are 2 persons A and B on FB . A should be able to view the pictures of B only if either A is friend of B or A and B have at least
one common friend . The interviewer discussed it for nearly 30 minutes . The discussion mainly included following points：- How are you going to store the list of friends for a given user?
- File system vs DB
- Given list of friends of 2 users, how are you going to find common friends?
- If you are going to store the friends in DB then how will the table look like?
- How many servers do you need?
- How are you going to allocate work to servers?
- How many copies of data will you need?
- What problems will you face if you are maintaining multiple copies of data.
- design structure for auto completion
- 如何实现search suggestions。
- 设计fb的系统支持like那个button
- design 股票#，time，price；-设计一个client side显示股票信息，给出尽可能多的user case
-在给出的user case里面，怎么设计客户端，使得客户段性能提高
-怎么设计server端
-数据如何传输
-server端如何保存数据
-怎么设计database table保存数据
-不用index怎么提高数据查询速度
-database是怎么实现数据查询的（要求从database implementation角度解释）
（1）（百度）要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。（题目还给出了一系列的数据，比如：站点数总共为5000万，IP地址有1000万，等等）
解决方案：DNS服务器实现域名到IP地址的转换。
每个域名的平均长度为25个字节（在域名的命名标准中，对于域名长度是有明显限制的。其中，中国国家域名不得超过20个字符，国际通用域名不得超过26个字符），每个IP为4个字节，所以Cache的每个条目需要大概30个字节。
总共50M个条目，所以需要1.5G个字节的空间。可以放置在内存中。（考虑到每秒5000次操作的限制，也只能放在内存中。）
可以考虑的数据结构包括hash_map，字典树，红黑树等等。
可以考虑的数据结构包括hash_map，字典树，红黑树等等。
我觉得比较好的解决方法是，将每一个URL字符串转化为MD5值，作为key，建立最大或最小堆，这样插入和查找的效率都是O(log(n))。
MD5是128bit的大整数也就是16byte，比直接存放URL要节省的多。
MD5是128bit的大整数也就是16byte，比直接存放URL要节省的多。
具体可应用方法：每秒5000的查询不算高啊，最土的方法使用MySQL+Memcached架构应该都能满足吧？
数据结构建议以域名的md5值为主键来存储，值可以只存储目标IP就行。Memcached用户支撑前端查询，MySQL用户存储数据，还要看总数量会有多大，如果不是特别大，直接使用MyISAM引擎来存储就行，更新插入都非常快，如果超千万，可以使用InnoDB来存储，每次有新数据插入时直接使用replace into table就行，Memcached数据的更新直接使用set。
Memcached随便用得好些，每秒上万次的get是容易达到的，MySQL你别小看，在有的测试里，以主键查询的测试，一台普通的服务器上，MySQL/InnoDB 5.1服务器上获得了750000+QPS的成绩。
Memcached随便用得好些，每秒上万次的get是容易达到的，MySQL你别小看，在有的测试里，以主键查询的测试，一台普通的服务器上，MySQL/InnoDB 5.1服务器上获得了750000+QPS的成绩。
总结：关于高并发系统设计。主要有以下几个关键技术点：缓存，索引，数据分片，锁粒度尽可能小。。
（2）有N台机器，M个文件，文件可以以任意方式存放到任意机器上，文件可任意分割成若干块。假设这N台机器的宕机率小于1/3，想在宕机时可以从其他未宕机的机器中完整导出这M个文件，求最好的存放与分割策略。
解决方案：涉及到现在通用的分布式文件系统的副本存放策略。一般是将大文件切分成小的block（如64MB）后，以block为单位存放三份到不同的节点上，这三份数据的位置需根据网络拓扑结构配置，一般而言，如果不考虑跨数据中心，可以这样存放：两个副本存放在同一个机架的不同节点上，而另外一个副本存放在另一个机架上，这样从效率和可靠性上，都是最优的（这个google公布的文档中有专门的证明，有兴趣的可参阅一下。）。如果考虑跨数据中心，可将两份存在一个数据中心的不同机架上，另一份放到另一个数据中心。
（3）假设有三十台服务器，每个上面都存有上百亿条数据（有可能重复），如何找出这三十台机器中，根据某关键字，重复出现次数最多的前100条？要求用Hadoop来做。
-- not work
方案：针对每一台机器有100亿，类似100万时的处理方法，对数据进行切片，可以都切为100万的记录，对100万、取最前100，不同在于这前100也存入hash，如果key相同则合并value，显然100亿的数据分割完后的处理结果也要再进行类似的处理，hash表不能过长，原理其实也就是map和reduce。然后合并这30台机器的结果。
（4）设计一个系统，要求写速度尽可能高，说明设计原理。
解决方案：涉及到BigTable的模型。主要思想是将随机写转化为顺序写，进而大大提高写速度。具体是：由于磁盘物理结构的独特设计，其并发的随机写（主要是因为磁盘寻道时间长）非常慢，考虑到这一点，在BigTable模型中，首先会将并发写的大批数据放到一个内存表（称为“memtable”）中，当该表大到一定程度后，会顺序写到一个磁盘表（称为“SSTable”）中，这种写是顺序写，效率极高。说到这，可能有读者问，随机读可不可以这样优化？答案是：看情况。通常而言，如果读并发度不高，则不可以这么做，因为如果将多个读重新排列组合后再执行，系统的响应时间太慢，用户可能接受不了，而如果读并发度极高，也许可以采用类似机制。
（5）设计一个高并发系统，说明架构和关键技术要点。
方案：分布式系统中的核心的服务器的实现。可以是http服务器，缓存服务器，分布式文件系统等的内部实现。下边主要从一个高并发的大型网站出发，看一个高并发系统的设计。下边是一个高并发系统的逻辑结构：
1）缓存系统：缓存是每一个高并发，高可用系统不可或缺的模块。常见的缓存系统：Squid(前端缓存)、Ehcache(对象缓存系统)，动态页面静态化（页面缓存）
2）负载均衡系统：负载均衡策略有随机分配，平均分配，分布式一致性hash等。软件负载均衡有：基于DNS的负载均衡、基于LVS的负载均衡和基于lptables的负载均衡。硬件负载均衡：路由上配置nat实现负载均衡、对万网一个虚拟ip，内网映射几个内网ip。数据库负载均衡：数据库集群等。
（6）有25T的log(query->queryinfo)，log在不段的增长，设计一个方案，给出一个query能快速返回queryinfo？
方案：1）建立适当索引；2）优化sql语句；3）实现小数据量和海量数据的通用分页显示存储过程；4）合理选择聚集索引
以上所有问题中凡是不涉及高并发的，基本可以采用google的三个技术解决，分别为：GFS，MapReduce，Bigtable，这三个技术被称为“google三驾马车”，google只公开了论文而未开源代码，开源界对此非常有兴趣，仿照这三篇论文实现了一系列软件，如：Hadoop、HBase、HDFS、Cassandra等。
在google这些技术还未出现之前，企业界在设计大规模分布式系统时，采用的架构往往是database+sharding+cache，现在很多公司（比如taobao，weibo.com）仍采用这种架构。在这种架构中，仍有很多问题值得去探讨。如采用什么数据库，是SQL界的MySQL还是NoSQL界的Redis/TFS，两者有何优劣？ 采用什么方式sharding（数据分片），是水平分片还是垂直分片？据网上资料显示，weibo.com和taobao图片存储中曾采用的架构是Redis/MySQL/TFS+sharding+cache，该架构解释如下：前端cache是为了提高响应速度，后端数据库则用于数据永久存储，防止数据丢失，而sharding是为了在多台机器间分摊负载。最前端由大块大块的cache组成，要保证至少99%（该数据在weibo.com架构中的是自己猜的，而taobao图片存储模块是真实的）的访问数据落在cache中，这样可以保证用户访问速度，减少后端数据库的压力，此外，为了保证前端cache中数据与后端数据库中数据一致，需要有一个中间件异步更新（为啥异步？理由简单：同步代价太高。异步有缺定，如何弥补？）数据，这个有些人可能比较清楚，新浪有个开源软件叫memcachedb（整合了Berkeley DB和Memcached），正是完成此功能。另外，为了分摊负载压力和海量数据，会将用户微博信息经过片后存放到不同节点上（称为“sharding”）。
这种架构优点非常明显：简单，在数据量和用户量较小的时候完全可以胜任。但缺定早晚一天暴露出来，即：扩展性和容错性太差，维护成本非常高，尤其是数据量和用户量暴增之后，系统不能通过简单的增加机器解决该问题。
于是乎，新的架构便出现了。主要还是google的那一套东西，下面分别说一下：
GFS是一个可扩展的分布式文件系统，用于大型的、分布式的、对大量数据进行访问的应用。它运行于廉价的普通硬件上，提供容错功能。现在开源界有HDFS(Hadoop Distributed File System)，该文件系统虽然弥补了数据库+sharding的很多缺点，但自身仍存在一些问题，比如：由于采用master/slave架构，因而存在单点故障问题；元数据信息全部存放在master端的内存中，因而不适合存储小文件，或者说如果存储的大量小文件，那么存储的总数据量不会太大。
MapReduce是针对分布式并行计算的一套编程模型。他最大的优点是：编程接口简单，自动备份（数据默认情况下会自动备三份），自动容错和隐藏跨机器间的通信。在Hadoop中，MapReduce作为分布计算框架，而HDFS作为底层的分布式存储系统，但MapReduce不是与HDFS耦合在一起的，你完全可以使用自己的分布式文件系统替换掉HDFS。当前MapReduce有很多开源实现，如Java实现Hadoop MapReduce，C++实现Sector/sphere等，甚至有些数据库厂商将MapReduce集成到数据库中了。
BigTable俗称“大表”，是用来存储结构化数据的，个人觉得，BigTable在开源界最火爆，其开源实现最多，包括：HBase，Cassandra，levelDB等，使用也非常广泛。
除了google的这三家马车，还有其他一些技术：
Dynamo：亚马逊的key-value模式的存储平台，可用性和扩展性都很好，采用DHT（Distributed Hash Table）对数据分片，解决单点故障问题，在Cassandra中，也借鉴了该技术，在BT和电驴的中，也采用了类似算法。
虚拟节点技术：该技术常用于分布式数据分片中。具体应用场景是：有一大坨数据（maybe TB级或者PB级），我们需按照某个字段（key）分片存储到几十（或者更多）台机器上，同时想尽量负载均衡且容易扩展。传统的做法是：Hash(key) mod N，这种方法最大缺点是不容易扩展，即：增加或者减少机器均会导致数据全部重分布，代价忒大。于是乎，新技术诞生了，其中一种是上面提到的DHT，现在已经被很多大型系统采用，还有一种是对“Hash(key) mod N”的改进：假设我们要将数据分不到20台机器上，传统做法是hash(key) mod 20，而改进后，N取值要远大于20，比如是20000000，然后我们采用额外一张表记录每个节点存储的key的模值，比如：
node1：0~1000000
node2：1000001~2000000
。。。。。。
这样，当添加一个新的节点时，只需将每个节点上部分数据移动给新节点，同时修改一下这个表即可。
Thrift：Thrift是一个跨语言的RPC框架，分别解释一下“RPC”和“跨语言”，RPC是远程过程调用，其使用方式与调用一个普通函数一样，但执行体发生在远程机器上。跨语言是指不同语言之间进行通信，比如c/s架构中，server端采用C++编写，client端采用PHP编写，怎样让两者之间通信，thrift是一种很好的方式。
设计一个只读的lookup service. 后台的数据是10 billion个key-value pair, 服务形式是接受用户输入的key，返回对应的value。已知每个key的size是0.1kB，每个value的size是1kB。要求系统qps >= 5000，latency < 200ms.
server性能参数需要自己问，我当时只问了这些，可能有需要的但是没有问到的……
commodity server
8X CPU cores on each server
32G memory
6T disk
使用任意数量的server，设计这个service
http://www.duweiwen.com/wechat/337755882288ee.html
优秀的面试者
类别：极少见
是否聘用建议：一旦发现，马上聘用
一个优秀的面试者，在面试系统设计题时，只需通过自主地向面试官询问并厘清系统设计需求，就可以相对独立地完成面试题，并不需要面试官的太多帮助。通常，这类优秀的面试者，他们这么答系统设计题：先描述一个大的设计框架，然后给出更多的details。这类优秀的面试者，给出的系统设计常常是非常make sense的，以致于面试官都很难“找茬”。当面试官要求该面试者解释部分的设计时，该面试者可以非常清楚、准确地描述这个设计部分是如何works的。如果面试官要求面试者拓展整个设计(expand the design)，面试者也能非常清楚地修正/或重新设计他先前的设计。
合格的面试者
类型：常见
是否聘用建议：如果其他的面试轮表现得也不错，就聘用
一个合格的面试者会尝试跟面试官沟通并厘清系统设计需求，然后从一个high level 的层面开始系统设计。这类求职者在面试过程中或多或少会犯一些错误。但是，一旦面试官指出他系统设计中的错误时，这类面试者可以非常快地修正他的设计。当面试官要求他解释其中的某部分设计时，这类求职者也通常可以不费力地描述和解释自己的设计。这类求职者，对于系统设计有一个high level的想法，同时也可以针对新需求进行改进。这类求职者提供的系统设计或许看起来有些蹩脚，但总体来说，应该是一个看起来在现实中可work的产品。
比较差的面试者
类型：常见
是否聘用建议：如果是一个完全没接触过系统设计的面试者，比如New Grads，可以考虑hire
一个比较差的面试者，在拿到系统设计题目时，会直接开始设计，而忽略了与面试官沟通并澄清设计需求的过程。所以他们在设计时，通常会有很多错误。当面试官指出其中的设计错误时，比较差的求职者，他们往往没有能力进行修正。当面试官要求面试者修正或拓展整个设计时，比较差的求职者也没办法去改进原先的设计，或者缺乏相关的知识。比较差的面试者，他们不太能给出一个完善的设计，而常常是非常蹩脚的。
糟糕的面试者
类型：极少见
是否聘用建议：不聘用
一个糟糕的面试者在拿到系统设计题时，通常不知道如何入手。他们不能自己把系统设计问题break down，而需要面试官来帮忙。当面试官让他们只设计某一小部分时，他们可以做出很好的设计，但是无法全面、完整地考虑整个project的设计(think the project as a whole)。这类面试者需要面试官给很多很多的hints才能给出一个设计，或者他们给出的设计，在现实中完全就是不可行的。
小结
在《系统设计班》，我们的老师反复强调，面试者在做系统设计题时，一定要先给出一个work solution，然后再去优化它。
http://chuansong.me/n/505197049961
Facebook 的 System Design 面试时长为45分钟，主要考察是是，求职者能否处理 Large Scale 的问题。在面试过程中，面试官会让你为Facebook设计一个feature。通过设计一个负责的系统，面试官主要是想考察你在 consistency, availability 和 partition tolerance 之间如何做 tradeoff，进而评估你的思考、实践能力。在这里，Facebook HR 着重要求面试者，一定要看以下的资料：
【1】Dropbox Large Scale 相关视频：http://t.cn/zQUvcsq
【2】Facebook 关于Scaling Memcache的文章：http://bit.ly/1zqgW4p
以上HR列出的内容，在本周末的九章算法《系统设计班》免费试听课也会讲到哦（美西8月14日周日早上10-12点）。《系统设计班》第一节免费试听课将讲解如何设计类似Instagram、Facebook、Twitter 这样的社交网络，他们的系统设计原理，以及如何进行Large Scale 处理等
其次，HR姐姐还给出了一些可能会考到的系统设计热门topic哦：
【1】Concurrency (threads, deadlock, starvation, consistency, coherence)
【2】Abstraction (understanding how OS, filesystem, and database works)
【3】Real-world performance (relative performance RAM, disk, your network, SSD)
【4】Availability and Reliability (durability, understanding how things can fail)
【5】Datastorage (RAMvs. durablestorage, compression, byte sizes)
系统是非常复杂的。当你在设计一个系统时，你必须直面所有的复杂性。基于这一点，你必须熟知以下内容：
- 并发性(concurrency)。你知道线程(threads)、死锁（deadlock）和starvation吗？你知道如何并行化算法吗？你了解一致性(consistency)和连贯性(coherence)吗？你大概了解IPC和TCP/IP吗？你知道吞吐量（throughput） 和延迟（latency）的区别吗？
- 现实表现(real-word performance)。你应当熟悉你电脑的速度和性能，包括RAM、硬盘、SSD以及你的网络状况。
- 估计(estimation)。估计在帮助你缩小可能性解决方案的范围时起到了重要的作用。这样，你就只需写少数几个原型或微基准。
- 可用性和可靠性(availability and reliability)。你是否考虑过系统什么时候会出现bug无法运行吗（特别是在分散式的环境中）？你知道如何设计一个系统以应当网络故障吗？你了解持久性吗？切记，我们并不是要寻找一个熟悉以上所有的问题的“全才”。我们想衡量的是你的熟练程度。我们只需要你对系统设计方面有一定的基础，并且知道什么时候应该寻求专家的帮助。
http://www.wzaobao.com/p/j2fBlt.html
1. 设计一个牌类游戏 OOD
2. 设计一个服务监视系統。说你有一堆服务器和一堆服务，怎么监视服务状态。 系统设计。各种情况。各种要求。
3. 设计一个企业内部用的那种日志系统。大概的用途是A发现一个什么问题，log问题，相关的人会接到通知。半系统半OOD。中间面试我的人想给我点提醒。说中间某部分可以用某种design pattern来做。不过那个design pattern不是factory singleton observer strategy等几个常见的。所以提示了和没提示一样。
4. 设计一个和配置相关的系统。大概的功能是比如A要买你的软件，人家可能不需要把你所有的功能买走。他提出了一些他想实现的功能，然后你把你内部的一些模块啥的拼一拼然后给人家。这样一个系统怎么设计。
第一题基本还有个参照。按CC150思路走的。不过也被拍死了。cc150的结构大概适合于赌场游戏。他说如果像UNO那种。你这个设计就不行。直接就傻逼了。时间也到了。这个里面让做了个洗牌。然后讨论为什么我的洗法能够实现纯随机。就是可以等概率的洗出任意一种可能。
http://yuanhsh.iteye.com/blog/21864572) design
解这种题是个*交流*的过程，或者说是给出方案然后获取反馈的不断循环的过程。
一般的流程：
首先你要问清楚requirement；
然后可以讲一下high level architecture，就是分成哪几个component，互相之间如果
interact，在白板上画一画；
之后面试官可能会让你深入某个component detail讨论；
也有可能变换requirement让你重新设计
另外，f家还喜欢让你估算机器之类的，做一些back-of-envelopme calculation。所以
最好对一些计算机相关的基本常数，fb的用户量等等有个大概的了解。
准备的时候建议看看fb的design高频题。一方面有可能面试的时候刚好碰到这几个
topic，另一方面其实很多design都是相通的。
http://geekband.com/course/1029
二.系统设计中七剑客
7.同步
8.网络
9.数据库
10.分布式
11.性能
12.估算
13.面向对象
14.案例
· 设计网站信息流设计
· 日志统计
· 产品页面设计
三.搭建大规模可扩展的系统
15.分布式系统
16.数据库系统
17.经典架构 (master/slave)
18.设计原则：CAP理论
19.一致性介绍
20.关系型数据库
21.ACID vs. BASE
22.sharding分片
23.一致性hash
24.NoSQL数据库
25.Cassandra
26.实时系统：Kafka, Storm
27.案例：
· 电商网站设计
· 网页爬虫设计
四.大数据系统
28.大数据基础：Hadoop，Spark入门
29.教你如何看懂MapReduce，BigTable，GFS三篇paper
30.聊天系统设计
31.估算机器
32.其他常见面试中的设计题目
