祝大家面试顺利
虽然不同公司的面试各不相同，但是对于软件开发这个职位来说，绝大部分面试内容都属于以下几大类：项目介绍、算法、设计和数学或智力题。
其中项目介绍取决于面试者之前的项目经历，重点是能把事情介绍清楚，有一些闪光点更好。而数学或智力题则太宽泛，提前复习和准备并不容易，不过在面试中被考察的几率也小，取决于公司和面试官。算法则是很多大公司面试的重中之重，设计次之。大部分面试者在面试之前都会突击算法，大家也都比较熟悉如何应对它们。而设计题，则往往被我们忽略，我曾就以为它就只能靠自己的经验和临场发挥了。直到工作快两年了，才从这个网站得知面试中解答设计题的正确姿势是这样的。
简介（Introduction）
这是HiredInTech上的一个简短的课程，主要讲解的就是如何应对面试中的系统设计题。系统设计（System design）题要求面试者在较短的时间内设计出一个软件系统的高层架构，可能是web service, RESTful API或者Desktop app。例如，设计一款URL缩写系统；如果有机会，你会如何实现Google搜索引擎；基于客户端-服务器应用程序设计一款双人交互下象棋的应用；或者，设计一个算法在Facebook社交网络基础上向用户推荐好友等等。
首先要说的是，面对一道设计题，不管它是很大很难，还是比较具体比较容易，我们都要摆正心态。面对难题不要惊慌，按照下面的步骤一步一步地进行，不一定要给出一个绝对的答案，最重要的是思考的过程（毕竟很多系统需要公司里几十甚至几百个人花费几个月甚至几年）。而且设计题也是没有标准答案或者正确答案的，可能一道题目有多种解决方案，各有优劣，那就需要你根据应用场景的需求进行取舍。面对看起来非常简单的设计题时，也不要掉以轻心，自以为很了解地东一句西一句地介绍是不合时宜的。有可能你做过相关的事情，心里有一个很完美的解决方案，但是没有以很好的方式表现出来，面试官并不清楚你有很清晰的逻辑思维，岂不是很遗憾。所以，下次再遇到设计题，可以从下面几个方面进行思考或者阐述。
第一步：确定约束和适用场景（Constraints and Use Cases）
和解答算法题一样，设计题在开始着手思考解决方案之前，最好不断地向面试官提问，彻底搞清楚问题之后再开始解答。对于算法题，一个经典的例子是，面试官让写一个排序算法。你可以问需要对什么进行排序，整数？浮点数？字符串？然后面试官告诉你需要排序的是员工的年龄。那么问题就一下子简化了，你本来可能想着是写个快排还是归并排序呢？这下需求彻底搞清楚之后就可以用很简单的桶排序或者基数排序了。
所以，切记，正式开始解题前先彻底理解需求！首先，你需要弄清楚系统的限制，并找出一些系统需要适用的场景。有时候面试官会故意先把系统要求说得很含糊，他会期望看到，你面对难题时能否注意到系统的要求并在设计方案中解决它们。
以“URL-shortening service”为例，它可能只需要服务于几千个用户，但是每个用户可能有百万的URL；可能需要处理缩写后的URL上百万量级的点击，也可能只有几十。这里有一个例子是跟面试官确认之后细化的constraints和use cases。
"Design a url shortening service, like bit.ly"
Use Cases
1. Shortening: take a url => return a much shorter url
2. Redirection: take a short url => redirect to the original url
3. Custom url
4. High availability of the system
Constraints:
1. New URLs per month: 100 million
2. 1 billion requests per month
3. 10% from shortening and 90% from redirection
4. Requests per second: 400+ (40: shortens, 360: redirects)
5. 6 billion urls in 5 years
6. 500 bytes per URL
7. 6 bytes per hash
8. 3TBs for all urls, 36 GB for all hashes (over 5 years)
9. New data written per second: 40 * (500 + 6): 20 K
第二步：抽象设计（Abstract Design）
完成了第一步之后，你大概就清楚了你要设计的系统以及所需解决的具体问题。所以，接下来你要给出一个高层的抽象设计。你需要列出这个系统所需要的所有重要组件，以及各个组件之间的联系，有条件的话可以画一个草图。
这个时候面试官可能会给你一些反馈，你可以反驳或者修改你的高层设计，但是绝对不要被他引入到具体细节的讨论中去。在介绍抽象设计时可以返回去检查一下，所有的use cases是不是都被覆盖了。
下面是“RL-shortening service”的抽象设计。
Abstract Design:
1. Application service layer (serves the requests)
* Shortening service
* Redirection service
2. Data storage layer (keeps tract of the hash => url mappings)
* Acts like a big hash table: stores new mappings,
and retrieves a value given a key.
第三部：找到瓶颈（Understanding Bottlenecks）
一般情况下，我们不大可能立即找到一个完美的设计，如果发现你的设计在某些情况下不能正常处理或者可能会有性能问题，也不要急于推翻它。这一步，我们要做的就是找到抽象设计里的这些瓶颈，然后对它们进行分析，尝试提出解决方案。如果设计中存在多处瓶颈问题，也不一定要全部分析，面试官感兴趣的话可能会跟你深入探讨其中一个。值得一提的是，有时候你的解决方案可能解决了刚提到的瓶颈，但是又会引入新的问题，这时候也不要急于否定。你可以根据前面列出use cases和constraints来分析不同的问题对系统的影响，权衡具体的解决方案。
对于上面的例子，根据我们在第一步分析的结果来看，Traffic (400+ requests per second)或者lots of data (3TBs for all urls, 36 GB for all hashes)可能是瓶颈。然后详细分析每个问题，流量可能并没有什么大问题，我们可能对数据更感兴趣，接着就可以深入讨论数据问题了。
第四部：扩展抽象设计（Scaling Your Abstract Design）
接下来就是详细扩展你的设计来解决这些瓶颈了。这里需要用到的就是一些常用的扩展原则，这就需要靠平时的积累了。
首先，需要了解一些关于scalability的理论知识。例如，一些基本概念：Vertical scaling、Horizontal scaling、Caching、Load balancing、Database replication、Database partitioning。或者负载均衡、多用户、大数据的处理方案等。
然后，可以参考High Scalability上介绍的一些有名的公司解决一些棘手提问的方法。并且在看的时候多留意他们用什么方法解决了什么问题，这些解决方案涉及到的理论方法等。另外，还可以从自己从事的项目中总结经验，遇到的问题，最后采用的解决方案，这些亲身经历的事情可能会感触更深吧。
继续回到上面的例子，这里是扩展的示例，更多详情请移步原文观看视频解说。
Scalable design:
1. Application Service Layer
* Start with one machine
* Measure how far it takes us (load tests)
* Add a load balancer + a cluster of machines over time:
to deal with spike-y traffic, to increase availability
2. Data Storage Layer
* Use one MySQL table with two varchar fields
* Create a unique index on the hash (36 GB+).
We want to hold it in memory to speed up lookups.
* Vertical scaling of the MySQL machine for a while
* Eventually, partition the data
by taking the first char of the hash mod the number of partitions
* Think about a master-slave setup
(reading from the slaves, writes to the master)
最后：总结（Summary）
面试的时候一般第四步还没有彻底讨论完，可能已经到时间了。不过，如果时间还有富余，可以把上述四步中的具体结果再总结一下。无论是远程还是现场面试，总结的时候把每步结果都写下来，不仅反映了你很清晰的条理和总结能力，还给面试官事后给你写评价提供了素材。
下面是原文中对上述四点的总结：
- Scope the problem: Don't make assumptions; Ask questions; Understand the constraints and use cases.
- Sketch up an abstract design that illustrates the basic components of the system and the relationships between them.
- Think about the bottlenecks these components face when the system scales.
- Address these bottlenecks by using the fundamentals principles of scalable system design.
网友评论