系统设计总结

转载

我的面试也结束了 因为知道FLAG这类公司都会问到System Design的问题 所以这次面试着重准备了一下 在这里分享给大家 如果有不对或者需要补充的地方 大家可以留言

这里说的System Design和OO Design不同 System Design在FLAG以及很多大公司中主要是design scalable distributed systems 这里只讨论如何准备这种题目

== 入门 ==
对于0基础的同学们 下面的资料可以按顺序开始看
1. http://www.hiredintech.com/app#system-design
这是一个专门准备面试的网站 你只用关心system design部分 有很多的link后面会重复提到 建议看完至少一遍

2. https://www.youtube.com/watch?v=-W9F__D3oY4
非常非常好的入门资料 建议看3遍以上！
这是1里面提到的资料 是Harvard web app课的最后一节 讲scalability 里面会讲到很多基础概念比如Vertical scaling, Horizontal scaling, Caching, Load balancing,Database replication, Database partitioning 还会提到很多基本思想比如avoid single point of failure
再强调一遍 非常好的资料！

3. http://www.lecloud.net/post/7295452622/scalability-for-dummies-part-1-clones
1里面提到的 Scalability for Dummies 还算不错 可以看一遍 知道基本思想

结束语：当你结束这一部分的学习的时候 你已经比50%的candidate知道的多了(因为很多人都不准备 或者不知道怎么准备system design) 恭喜

== 进阶 ==
这一部分的资料更加零散 每个看的可能不一样 但是你每多看一篇文章或者一个视频
你就比别人强一点
这部分你会遇到很多新名词 我的建议是每当你遇到一个不懂的概念时 多google一下
看看这个概念或者技术是什么意思 优点和缺点各是什么 什么时候用 这些你都知道以
后 你就可以把他运用到面试中 让面试官刮目相看了

4. http://highscalability.com/blog/ ... -coming-of-the.html
Database Sharding是一个很重要的概念 建议看一看

5. http://highscalability.com/all-time-favorites/
这个里面会讲到很多非常流行的网站架构是如何实现的 比如Twitter, Youtube,
Pinterest, Google等等 我的建议是看5-6个 然后你应该已经建立起了一些基本的意识
还有知道了某些技术和产品的作用和mapping 比如说到cache你会想到memcached和
Redis 说到
load balancer你会想到 Amazon ELB, F5一类的

6. http://www.infoq.com/
5里面很多的文章都会有链接 其中有很多会指向这个网站 这里面有很多的tech talk
很不错 可以看看

7. https://www.facebook.com/Engineering/notes
Facebook非常好的技术日志 会讲很多facebook的feature怎么实现的 比如facebook
message:https://www.facebook.com/notes/f ... ing/the-underlying-
technology-of-messages/454991608919 建议看看 尤其是准备面facebook的同学

8. 一些国内网站上的资料
http://blog.csdn.net/sigh1988/article/details/9790337
http://blog.csdn.net/v_july_v/article/details/6279498

9. 最后一些概念很有用 都是我再看这些资料的时候发现的 如果你没有遇到或者查过
建议查查
Distributed Hash Table
Eventual Consistency vs Strong Consistency
Read Heavy vs Write Heavy
Consistent Hashing

== 小结＝＝
看多了以后 你的最终目标应该是心里有了一个大框架 一个基本的distributed system
是怎么搭起来的 然后心里有很多if condition 如果要是满足这个条件 我应该用什么
技术 比如如果read heavy那么用cache会提升performance之类的 同时知道应该避免什
么东西 比如避免single point of failure 再比如时间和空间的tradeoff在read
heavy的时候应该倾向于时间 Write heavy的时候倾向于空间等等

你总结出来的和我总结出来的大框架和if conditions肯定不完全一样 但因为system
design本来就是一个open ended question 所以不用害怕 能够自圆其说 就不会有问题

最后 本文纯属抛砖引玉 如果有大牛发现有错误或者有补充 欢迎留言 大家一起讨论

== FAQ ==
1. New Grad需要看System Design么?
答案是it depends. 有的公司会考system design 有的公司只考到OO design 有的公司
压根不考 当然 考到的公司对new grad的期望值会稍微低一点 但是 你有这么一个机会
能让你gain leverage over other candidates why not? 为什么要让自己在面试前害怕
面试官出system design的题目呢?

系统设计知识考察点

比如面向对象，接口设计，设计模式，数据库表，分布式。

首先在性能耗在什么地方之前不要优化。所谓杞人忧天，你不是百度或者facebook的流量，根本考虑不到很多细节，大多数直接用云计算平台，直接帮你做了。但面试中还是会考察。

这里就针对Scalability，有一些常见的优化技术，我就把他们列出。

Cache：缓存，万金油，哪里不行优先考虑
Queue：消息队列，常见使用Linkedin的kafka
Asynchronized：批处理＋异步，减少系统IO瓶颈
Load Balance: 负载均衡，可以使用一致性hash技术做到尽量少的数据迁移
Parallelization：并行计算，比如MapReduce
Replication：提高可靠性，如HDFS，基于位置感知的多块拷贝
Partition：数据库sharding，通过hash取摸

系统设计面试题思路综述

转载

在面试的时候，偶尔也会遇到一些系统设计题，而这些题目往往只是考一下你的知识面，或者对系统架构方面的了解，不会涉及编码。很多人感觉难以应对这样的题目，也不知道从何说起，在本文中，作者总结了回答这类题目需要哪些基础知识，以及怎样使用这些知识回答这些问题。由于作者写本篇文章时仅是一个刚找完工作的研三学生，还未真正参与设计过已经投入使用的系统，因此难免写得过于片面或者肤浅，请即将找工作的师弟师妹们仅作参考。

在正式介绍基础知识之前，我先罗列几个常见的系统设计相关的笔试面试题。
(1) 要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。（题目还给出了一系列的数据，比如：站点数总共为5000万，IP地址有1000万，等等）
(2) 有N台机器，M个文件，文件可以以任意方式存放到任意机器上，文件可任意分割成若干块。假设这N台机器的宕机率小于1/3，想在宕机时可以从其他未宕机的机器中完整导出这M个文件，求最好的存放与分割策略。
(3) 假设有三十台服务器，每个上面都存有上百亿条数据（有可能重复），如何找出这三十台机器中，根据某关键字，重复出现次数最多的前100条？要求用Hadoop来做。
(4) 设计一个系统，要求写速度尽可能高，说明设计原理。
(5) 设计一个高并发系统，说明架构和关键技术要点。
(6) 有25T的log(query->queryinfo)，log在不段的增长，设计一个方案，给出一个query能快速反回queryinfo

以上所有问题中凡是不涉及高并发的，基本可以采用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是一种很好的方式。

文章最前面的几道题均可以映射到以上几个系统中的某个模块中，如：

（1） 关于高并发系统设计。主要有以下几个关键技术点：缓存，索引，数据分片，锁粒度尽可能小。

（2） 问题2涉及到现在通用的分布式文件系统的副本存放策略。一般是将大文件切分成小的block（如64MB）后，以block为单位存放三份到不同的节点上，这三份数据的位置需根据网络拓扑结构配置，一般而言，如果不考虑跨数据中心，可以这样存放：两个副本存放在同一个机架的不同节点上，而另外一个副本存放在另一个机架上，这样从效率和可靠性上，都是最优的（这个google公布的文档中有专门的证明，有兴趣的可参阅一下。）。如果考虑跨数据中心，可将两份存在一个数据中心的不同机架上，另一份放到另一个数据中心。

（3）问题4涉及到BigTable的模型。主要思想是将随机写转化为顺序写，进而大大提高写速度。具体是：由于磁盘物理结构的独特设计，其并发的随机写（主要是因为磁盘寻道时间长）非常慢，考虑到这一点，在BigTable模型中，首先会将并发写的大批数据放到一个内存表（称为“memtable”）中，当该表大到一定程度后，会顺序写到一个磁盘表（称为“SSTable”）中，这种写是顺序写，效率极高。说到这，可能有读者问，随机读可不可以这样优化？答案是：看情况。通常而言，如果读并发度不高，则不可以这么做，因为如果将多个读重新排列组合后再执行，系统的响应时间太慢，用户可能接受不了，而如果读并发度极高，也许可以采用类似机制。

HRT面经

转载

来美国差不多一年半了，喜怒哀乐，不一而足。兜兜转转之后，找到了自己满意的工作，在这里记录下来，希望对后来者找工作能有一些帮助。我没有写非常详细的面经，是因为几乎所有题目都能在网上搜索到，再重复也没有多大意义（搜索也是一种能力），并且指哪打哪的面经几乎是小概率事件，充分的积累才是关键，希望大家理解。

实习结束回到匹兹堡以后，开始正式找全职。寒假的时候用Java刷了当时的Leetcode, 这时候我又用了大概10天的时间重新刷了大概200道leetcode（用c++），把状态转换到了刷题模式。9月初找内推，但发现事情进展并不顺利：

Facebook内推后拖到10月丢给我拒信。

Linkedin因为我实习自己海投过简历不能内推。

Pinterest同学内推以后毫无反应。

也有好消息。首先是很快就收到暑假实习的公司Pure Storage的return offer，吃了一颗定心丸（神奇的是，我知道的某大牛在PureStorage实习居然没有拿到，看来实习的组和mentor非常重要）。

Google的CMU recruiter联系了我，直接去Google Pittsburgh先面了两轮。大概是因为比较缺觉，现场面得一塌糊涂，据说在borderline上，所以过了大概两周才收到下一轮的通知，再去GooglePIT 面4轮。

题目不算特别诡异， 一道设计Tic-Tac-Toe游戏，一道大概是树上的搜索，一道有序数组找出现超过1/4次数的数字（主角光环，半年前和朋友吃饭听朋友提起过），一道throttlingapi requests的题目。我觉得自己发挥不错，精神上也足够重视，除了第二轮的面试官面瘫以外，跟其他面试官聊得都很开心。满以为肯定会有offer，岂料等来的是一封拒信。我的本意是用别家offer让Googlematch最后去Google家，只能说造化弄人。

Snapchat找了一个双料校友内推，先面一轮google hang out，一道是binarysearch tree combination count， 另一道忘掉了。虽然面我的中国大哥一直看起来不太开心，但还是顺利送我去onsite。Snapchat本身位置在LA，可以说既是优点也是缺点，离湾区大部队远，但Venice这个地方艺术气息非常赞，1分钟步行距离到海滩。海滩前面有个很大的滑板场地（如果大家看过精灵旅社2，里面有个滑板的场景就是Snapchat的实景，一模一样），大白天大家都光着膀子穿着沙滩裤到处溜达。

面试感觉自己发挥一般般，是在自己的笔记本上写，第一轮写string表示的浮点数的加法，写得各种惨，最后都有bug没改掉，第二轮写bloomfilter，面试官给了充分的提示，所以完全不用担心自己不知道或者不记得，但我居然忘了怎么传递方法指针了，惨。第三轮写一个公司层级表示。第四轮写一个board从一点到另外一点k步的path的计数。我见过别人面经里面面得比我好的悲剧的，所以心情还是很忐忑。第二天就收到了offer，赞hr效率。

Uber找了一个CMU校友内推，很快收到电面通知。题目是设计一个牌类游戏，需要写代码的就是shuffle部分。我忘了随机数如何生成了，惨，但小哥表示不是问题。Uber虽然人称HR反应神速，但是我过了很久以后才收到让我onsite的通知，拿offer催都没有用。

这周二刚刚面完。第一轮是word break，第二轮是一个迭代定义的object（可以是int,可以是arrayof objects）的构造方法实现，第三轮是一个database duplicate的实现（题目很简单，最后的考点是如何解决环状结构），第四轮manager面，聊到最后问了我一个debug电话的问题，完全没有头绪，最后他微微一笑告诉我答案其实是该电话的号码不是他号称的那个号码，吐血三升。过了两天以后内推的大哥告诉我Moveto offer，和HR电话谈过，offer的细节要过两天告诉我。

某猎头推荐我去HRT（Hudson River Trading）,做了OA，题目不难但我有一个case没有全对，还是过了。电面两轮，内容包括网络（tcp等）、编程语言（我简历上java c++都有，于是被狂轰乱炸）、简历（聊得非常细节）以及神奇的脑筋急转弯。因为NDA的关系，我不能直接说题目，但和matrix67博客里面经常出现的那种有趣的题目非常接近，也和cs本身多少有点关系。我运气很好，脑筋急转弯的题目答得面试官很满意，然后给了onsite的机会。

HRT非常土豪，土豪到什么程度呢？所有的onsite candidate都送一块苹果表…我面完才知道的，极度震惊。公司本身在曼哈顿，30楼， 玻璃外就是一条河（hudson river?）。氛围感觉很不错，每个面试官我都多少感受到了geek的自负。有一轮coding，给你详细的算法说明让你实现某个算法。剩下三轮技术面试，非常类似于电话面试的内容，仍然在纠结网络、语言和简历，写代码部分很少或者说几乎没有。最后和老大讨论一下人生理想。 本来我只是用HRT练手的，我对这个公司一无所知，之前也从来没有考虑过去纽约工作，但是offer下来以后震惊了，整个package大约是25w。没办法，只能为金钱出卖灵魂了=-=

现在还和Two Sigma以及Airbnb约了onsite。飞机票都定好了，而且离deadline还远，我抱着了解的想法决定还是去把这两家面了。TwoSigma我做了OA就给了Onsite，OA大家一搜就有，没什么难度。Airbnb的面试是CMU 的oncampus，比较特殊，对大家应该没太大帮助，在此就不细说了。

感受很多。

海投真的是下下之选。一定要坚持不懈地找内推，找校友，找网上的陌生人，尽你一切可能去找。我自认为我的经历不算差了，但海投没有一次有反应的。

刷题是个持久战。不同人有不同的基础条件，但大概刷到什么程度就算差不多了呢？我觉得应该是：新题来了以后能很快定位出来这题是什么类型，老题对哪些地方会有坑以及自己写怎么避坑有丰富的经验。总结自己的模板。总结适合自己的经验。一开始看别人解答完全没有问题，我也是这么过来的，但一定要总结出来，有办法在自己记不清楚的情况下能引导自己想出来怎么写。Dfs,bfs, graph简单算法，简单贪心，一维二维dp，链表，binary search，树，自己用的语言的所有容器的api。知识点大概就这儿多，所谓刷题不过是强化自己对每个部分的熟悉程度，形成自己的写题套路。

以及坚持。每个人的背景有好有坏，你可能基础不好，可能课程繁重，可能情感纠葛，阻碍你的因素总会有很多，但坚持下去，到某个时间段，你自然会意识到，我已经准备好了。我知道我这一路走来很多时候有有赖于运气，但努力了没有得到回报的，以我所见，并不太多。问问你自己，是否尽了全力。尽了全力，再怪运气。

最后感谢我的父母，虽然他们在国内对美国和我的行业一无所知，但一直都给予了我最大的信任和支持。感谢我的女朋友，她妥妥地看不到这篇文章，但她真的给予了我无限的力量。也感谢我自己。 我曾经风光无限，后来又堕入深渊，但好在亡羊补牢，为时不晚。

努力本身就是回报，与所有努力过和努力着的人共勉。

PMP考试心得-转载

2012年12月8日我参加了PMI的PMP认证考试，12月30日得知自己通过了考试，
于是决定写个心得同大家分享一下 。

1、培训前的准备工作

今年9月份时，公司发出信息说10月份会有PMP的相关培训，我也很荣幸的拿到了培训名额。在培训考试前的2个星期，我便在网上搜集PMP的相关资料，提前做准备。不过，这段时间的感觉就是，每个字都看得懂，整体连起来不怎么明白啥意思。基本上看过就忘了。现在回想，觉得参加集体培训很重要。

一方面，PMI要求PMP考生在考前必须参加35小时的项目管理培训课程，另一方面，参加培训班来系统地学习项目管理知识进行备考也是十分必要的。在老师的指导下学习，比自己看书，跟容易理解并记忆，也能很好的抓住重点。

2、参加培训课程

因为培训前已经完成考试注册，所以我还是抱着很认真的态度去培训。心里也有些忐忑，毕竟三千三呢，血汗钱啊。第一天的课，老邱讲课讲得很生动。PMP 联系四大名著，理论联系实际案例。一整天的课，上课却没有走神，很是happy。也听从了老师的建议，买了本张斌的PMPbok指导书。在之后的培训过程中，不得不承认这本书帮我很多，PMPBOK书的上文字很简单，有些知识点也是一句话带过，浮光掠影般的。但是白天听课，晚上跟着张斌的书，一个版块一个版块的做题，我通过这样的方式，对PMPbok的每章内容就有了更深的了解。预习，上课，复习，这个学习过程的重要性相信很多人都明白。不过有一点，很多人在预习的时候喜欢在书上写写画画。然后老师讲的时候，有些没画的，重点的，又画一点。最后在复习的时候，老邱又会给出一部分重点。到最后，我发现很多人的PMPBOK基本上全部都画上了，等于没有重点。所以，个人建议，还是注意保持书的清洁。


3. 考前复习

培训课程结束后。老邱给我们安排了2天的复习课。拎重点。尽管有网络YY语音课程，我跟公司的其他两位同事，还是5点就从浦东往浦西赶，去参加现场版的。事实也证明我们的决定是对的。在现场，尤其是我们抢到了第一排的位置，这样听起来的效果真的很棒。

4. 模拟考试

下面就是3次模拟考了。第一次考试，160。哈哈，这个结果但是让我小得瑟了下。那后面的一周，看书也有点放松。结果到了第二次模拟，直接跌到了140。而且老邱也说了，3次模拟考，一次比一次难，真实的考试，最接近第三次的难度。最后两周的时间里面，我是每天地铁上听录音，背ITTO。在公司的时候，也是挤时间看PMPBOK。下班了留公司二个小时，把模拟卷子，不管对错，从头到尾的研究。这样轮番的看，找感觉。

5. 参加考试

考试前一天，说实话，我没有再花很多的时间去拼命的看书。我就仔细检查了自己的身份证，准考证，查好了去考场的路线，然后很早就休息了。毕竟，想要考好，充足的精神，清晰的脑袋很重要。

PMP结束了，看到自己成绩的时候，有一种总算没白辛苦的感觉。回头想想，考试其实不难。好好听课，认真做题。参加考前重点复习指导，3次模拟考试找感觉。一步步的跟着老师的安排认真走下来，再正常发挥下，基本上就可以拿到证书这个敲门砖了。之后再集PDU，把PMP培训学到的，结合到自己的生活工作当中，增加experience，提高自己的含金量。

在这里，很感谢交大慧谷培训中心的老邱。他真的很负责，对学员的服务很到位。而且言出必行，真的做到了从头到尾一直陪着学员走过。非常感谢！！

SDE面试技巧之一：OOA & OOD

这里不讨论OOA和OOD的具体技术，这里只是讨论面试过程中如何问、如何答。在掌握了OOD的具体技术后，要想面试成功，还需要掌握面试技巧。OOD的面试的时要特别注意Clarify the ambiguity，以避免你的设计既可以满足需求，又不会over design。

下面这一段摘自：http://www.nomachetejuggling.com/2010/04/06/avoiding-the-big-design-interview-question/，我觉得作者写的挺好的。

How To Ask This Question
If you want to know how comfortable a candidate is with OO, ask them the question in a way that resembles real-life OOP a bit more closely. Start simple, by providing a single simple requirement. Though the candidate won’t be able to write and run tests, the requirement serves as a driver for the design.
A good indicator that the question is taking you and the candidate off-track is if the boxes he or she draws on the whiteboard lack method names. If there are no methods, there are no behaviors, which means the candidate is designing first, regardless of requirements. Steer the candidate back by asking them to write method names.
For example, ask the candidate to design the object model for a simple bookshelf. A bookshelf is so simple that there’s virtually no way to overcomplicate it, so you can say that you simply need to be able to add a book to the bookshelf, nothing else. Once they have done this, give the candidate another “test”, by adding a requirement. Now say that you want the bookshelf to be a “smart” bookshelf, where you can look up a book by title and get a reference to the book. The candidate will make some changes to their design. Continue adding requirements to the thing until you’re satisfied with the evolution of the candidate’s design.

• Modify the design to allow me to search the bookshelf by Title, Author, or ISBN.
• Allow me to use the bookshelf as an ad-hoc library, so I can “check out” a book, removing it from the bookshelf. Make it possible to look up books that have been “borrowed”.
• Require a user provide their name when checking out a book. Give them a return date.
• Make it so the bookshelf can generate a list of overdue books and who has them. Where does that method belong? Should it be on its own object that Bookshelf uses?Make the bookshelf more concrete, so that there is only a certain number of books that can fit on any given shelf in the overall bookshelf. Make it possible to ask which shelf a book is on. Make it possible to add a new shelf.

You can obviously pick your own model (Car, Elevator, Fridge, etc) and drive the direction the design should go using requirements. Have the candidate write method names (but not implementations) where appropriate. Keep asking if the method is on the right object, or it belongs on another one.

How To Answer This Question
Of course, not everyone reads this blog, so if you’re in an interview you may get the “design an object model for a x” question. If you find yourself in this situation, you essentially want to ask questions of your interviewer to pull requirements out of them. The reality is, they probably DO have a particular kind of system in mind when they ask the question, so you need to find out what that is.
If you’re supposed to design the Car class, ask if there are other types of vehicles in the system. If not, don’t make a Vehicle parent class, and explain that you see no need unless the system required additional vehicles. Before you draw a box named Tire, ask if the car needs to be able to support snow tires or some other kind of interchangeable tire. If not, why would you make a class or interface for them? Start as simply as you can and only draw a new box when you’ve extracted enough information from the interviewer to deem it warranted. If you jump up to the whiteboard and draw two or three boxes before asking any questions, you’re placing your interview at risk because the interviewer may be picturing a completely different usage of this system than you are.
Of course, it’s always possible that the interviewer will keep asking for the same information, arguing that you should show your OO skills off without requirements that drive that design out. If you want the job, your best bet there is to take a random stab at the appropriate level of complexity and hope that you strike somewhere near what the interviewer wants. In that situation, however, I’d imagine your interviewer doesn’t know much about designing good software, and their codebase might be an over-engineered mess, so you may not want that job.

总体而言，我觉得面试的时候，应该是根据面试官的要求进行设计，废话？不！！！根据我个人的理解，设计是服务于特定目标的，没有哪个设计是可以满足所有场景的需要，因此在设计一个类或者考虑要不要继承时，就需要知道设计目标和场景，而这是完全来源于面试官的要求。如果面试官没有说，你想到的可以问，但不能自己进行假设。因为OOD中最主要的考察点就是看应聘者能不能发现那些不明确的、模棱两可的地方，通过问面试官的方式进行clarify。所以OOD面试题中，最重要的就是：不要自己假设，在考虑应不应该使用某种设计时，问面试官以确定各种条件是否符合！

http://www.cnblogs.com/whyandinside/archive/2012/10/26/2740612.html

Hadoop VS Spark

转载
我本人是类似Hive平台的系统工程师，我对MapReduce的熟悉程度是一般，它是我的底层框架。我隔壁组在实验Spark，想将一部分计算迁移到Spark上。

年初的时候，看Spark的评价，几乎一致表示，Spark是小数据集上处理复杂迭代的交互系统，并不擅长大数据集，也没有稳定性。但是最近的风评已经变化，尤其是14年10月他们完成了Peta sort的实验，这标志着Spark越来越接近替代Hadoop MapReduce了。Spark the fastest open source engine for sorting a petabyteSort和Shuffle是MapReduce上最核心的操作之一，比如上千个Mapper之后，按照Key将数据集分发到对应的Reducer上，要走一个复杂的过程，要平衡各种因素。Spark能处理Peta sort的话，本质上已经没有什么能阻止它处理Peta级别的数据了。这差不多远超大多数公司单次Job所需要处理的数据上限了。

回到本题，来说说Hadoop和Spark。Hadoop包括Yarn和HDFS以及MapReduce，说Spark代替Hadoop应该说是代替MapReduce。MapReduce的缺陷很多，最大的缺陷之一是Map ＋ Reduce的模型。这个模型并不适合描述复杂的数据处理过程。很多公司（包括我们）把各种奇怪的Machine Learning计算用MR模型描述，不断挖（lan）掘（yong）MR潜力，对系统工程师和Ops也是极大挑战了。很多计算，本质上并不是一个Map，Shuffle再Reduce的结构，比如我编译一个SubQuery的SQL，每个Query都做一次Group By，我可能需要Map，Reduce＋Reduce，中间不希望有无用的Map；又或者我需要Join，这对MapReduce来说简直是噩梦，什么给左右表加标签，小表用Distributed Cache分发，各种不同Join的Hack，都是因为MapReduce本身是不直接支持Join的，其实我需要的是，两组不同的计算节点扫描了数据之后按照Key分发数据到下一个阶段再计算，就这么简单的规则而已；再或者我要表示一组复杂的数据Pipeline，数据在一个无数节点组成的图上流动，而因为MapReduce的呆板模型，我必须一次一次在一个Map/Reduce步骤完成之后不必要地把数据写到磁盘上再读出，才能继续下一个节点，因为Map Reduce2个阶段完成之后，就算是一个独立计算步骤完成，必定会写到磁盘上等待下一个Map Reduce计算。上面这些问题，算是每个号称下一代平台都尝试解决的。

现在号称次世代平台现在做的相对有前景的是Hortonworks的Tez和Databricks的Spark。他们都尝试解决了上面说的那些问题。Tez和Spark都可以很自由地描述一个Job里执行流（所谓DAG，有向无环图）。他们相对现在的MapReduce模型来说，极大的提升了对各种复杂处理的直接支持，不需要再绞尽脑汁“挖掘”MR模型的潜力。有兴趣的童鞋可以看看这PPThttp://www.slideshare.net/Hadoop_Summit/w-235phall1pandey这是Hadoop峰会上Tez的材料，第九页开始有描述Hive on Tez和传统MR Hive的区别，这些区别应该也适用于MR Hive和Spark SQL，也很清楚的体现了为何MR模型很笨重。

相比Tez，Spark加入了更多内存Cache操作，但据了解它也是可以不Cache直接处理的，只是效率就会下降。再说Programming Interface，Tez的Interface更像MapReduce，但是允许你定义各种Edge来连接不同逻辑节点。Spark则利用了Functional Programming的理念，API十分简洁，相比MR和Tez简单到令人发指。我不清楚Spark如果要表现复杂的DAG会不会也变得很麻烦，但是至少wordcount的例子看起来是这样的，大家可以比较感受下：incubator-tez/WordCount.java at master · apache/incubator-tez · GitHubExamples | Apache Spark处理大规模数据而言，他们都需要更多proven cases。至少Hadoop MapReduce是被证明可行的。作为Data Pipeline引擎来说，MapReduce每个步骤都会存盘，而Spark和Tez可以直接网络发送到下一个步骤，速度上是相差很多的，但是存盘的好处是允许继续在失败的数据上继续跑，所以直观上说MapReduce作为pipeline引擎更稳健。但理论上来说，如果选择在每个完成的小步骤上加CheckPoint，那Tez和Spark完全能和现在的MapReduce达到一样的稳健。

总结来说，即便现在不成熟，但是并没有什么阻碍他们代替现有的MapReduce Batch Process。对Tez而言，似乎商业上宣传不如Spark成功。Databricks头顶Berkley的光环，商业宣传又十分老道，阵营增长极快。光就系统设计理念，没有太大的优劣，但是商业上可能会拉开差距。Cloudera也加入了Spark阵营，以及很多其他大小公司，可以预见的是，Spark会成熟的很快，相比Tez。但Tez对于Hortonworks来说是赢取白富美的关键，相信为了幸福他们也必须努力打磨推广tez。所以就算现在各家试用会有种种问题，但是毕竟现在也就出现了2个看起来有戏的“次世代”平台，那慢慢试用，不断观望，逐步替换，会是大多数公司的策略。