雖然不同公司的面試各不相同，但是對于軟件開發(fā)這個(gè)職位來說，絕大部分面試內(nèi)容都屬于以下幾大類：項(xiàng)目介紹、算法、設(shè)計(jì)和數(shù)學(xué)或智力題。
其中項(xiàng)目介紹取決于面試者之前的項(xiàng)目經(jīng)歷，重點(diǎn)是能把事情介紹清楚，有一些閃光點(diǎn)更好。而數(shù)學(xué)或智力題則太寬泛，提前復(fù)習(xí)和準(zhǔn)備并不容易，不過在面試中被考察的幾率也小，取決于公司和面試官。算法則是很多大公司面試的重中之重，設(shè)計(jì)次之。大部分面試者在面試之前都會突擊算法，大家也都比較熟悉如何應(yīng)對它們。而設(shè)計(jì)題，則往往被我們忽略，我曾就以為它就只能靠自己的經(jīng)驗(yàn)和臨場發(fā)揮了。直到工作快兩年了，才從這個(gè)網(wǎng)站得知面試中解答設(shè)計(jì)題的正確姿勢是這樣的。
簡介（Introduction）
這是HiredInTech上的一個(gè)簡短的課程，主要講解的就是如何應(yīng)對面試中的系統(tǒng)設(shè)計(jì)題。系統(tǒng)設(shè)計(jì)（System design）題要求面試者在較短的時(shí)間內(nèi)設(shè)計(jì)出一個(gè)軟件系統(tǒng)的高層架構(gòu)，可能是web service, RESTful API或者Desktop app。例如，設(shè)計(jì)一款URL縮寫系統(tǒng)；如果有機(jī)會，你會如何實(shí)現(xiàn)Google搜索引擎；基于客戶端-服務(wù)器應(yīng)用程序設(shè)計(jì)一款雙人交互下象棋的應(yīng)用；或者，設(shè)計(jì)一個(gè)算法在Facebook社交網(wǎng)絡(luò)基礎(chǔ)上向用戶推薦好友等等。
首先要說的是，面對一道設(shè)計(jì)題，不管它是很大很難，還是比較具體比較容易，我們都要擺正心態(tài)。面對難題不要驚慌，按照下面的步驟一步一步地進(jìn)行，不一定要給出一個(gè)絕對的答案，最重要的是思考的過程（畢竟很多系統(tǒng)需要公司里幾十甚至幾百個(gè)人花費(fèi)幾個(gè)月甚至幾年）。而且設(shè)計(jì)題也是沒有標(biāo)準(zhǔn)答案或者正確答案的，可能一道題目有多種解決方案，各有優(yōu)劣，那就需要你根據(jù)應(yīng)用場景的需求進(jìn)行取舍。面對看起來非常簡單的設(shè)計(jì)題時(shí)，也不要掉以輕心，自以為很了解地東一句西一句地介紹是不合時(shí)宜的。有可能你做過相關(guān)的事情，心里有一個(gè)很完美的解決方案，但是沒有以很好的方式表現(xiàn)出來，面試官并不清楚你有很清晰的邏輯思維，豈不是很遺憾。所以，下次再遇到設(shè)計(jì)題，可以從下面幾個(gè)方面進(jìn)行思考或者闡述。
第一步：確定約束和適用場景（Constraints and Use Cases）
和解答算法題一樣，設(shè)計(jì)題在開始著手思考解決方案之前，最好不斷地向面試官提問，徹底搞清楚問題之后再開始解答。對于算法題，一個(gè)經(jīng)典的例子是，面試官讓寫一個(gè)排序算法。你可以問需要對什么進(jìn)行排序，整數(shù)？浮點(diǎn)數(shù)？字符串？然后面試官告訴你需要排序的是員工的年齡。那么問題就一下子簡化了，你本來可能想著是寫個(gè)快排還是歸并排序呢？這下需求徹底搞清楚之后就可以用很簡單的桶排序或者基數(shù)排序了。
所以，切記，正式開始解題前先徹底理解需求！首先，你需要弄清楚系統(tǒng)的限制，并找出一些系統(tǒng)需要適用的場景。有時(shí)候面試官會故意先把系統(tǒng)要求說得很含糊，他會期望看到，你面對難題時(shí)能否注意到系統(tǒng)的要求并在設(shè)計(jì)方案中解決它們。
以“URL-shortening service”為例，它可能只需要服務(wù)于幾千個(gè)用戶，但是每個(gè)用戶可能有百萬的URL；可能需要處理縮寫后的URL上百萬量級的點(diǎn)擊，也可能只有幾十。這里有一個(gè)例子是跟面試官確認(rèn)之后細(xì)化的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
第二步：抽象設(shè)計(jì)（Abstract Design）
完成了第一步之后，你大概就清楚了你要設(shè)計(jì)的系統(tǒng)以及所需解決的具體問題。所以，接下來你要給出一個(gè)高層的抽象設(shè)計(jì)。你需要列出這個(gè)系統(tǒng)所需要的所有重要組件，以及各個(gè)組件之間的聯(lián)系，有條件的話可以畫一個(gè)草圖。
這個(gè)時(shí)候面試官可能會給你一些反饋，你可以反駁或者修改你的高層設(shè)計(jì)，但是絕對不要被他引入到具體細(xì)節(jié)的討論中去。在介紹抽象設(shè)計(jì)時(shí)可以返回去檢查一下，所有的use cases是不是都被覆蓋了。
下面是“RL-shortening service”的抽象設(shè)計(jì)。
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）
一般情況下，我們不大可能立即找到一個(gè)完美的設(shè)計(jì)，如果發(fā)現(xiàn)你的設(shè)計(jì)在某些情況下不能正常處理或者可能會有性能問題，也不要急于推翻它。這一步，我們要做的就是找到抽象設(shè)計(jì)里的這些瓶頸，然后對它們進(jìn)行分析，嘗試提出解決方案。如果設(shè)計(jì)中存在多處瓶頸問題，也不一定要全部分析，面試官感興趣的話可能會跟你深入探討其中一個(gè)。值得一提的是，有時(shí)候你的解決方案可能解決了剛提到的瓶頸，但是又會引入新的問題，這時(shí)候也不要急于否定。你可以根據(jù)前面列出use cases和constraints來分析不同的問題對系統(tǒng)的影響，權(quán)衡具體的解決方案。
對于上面的例子，根據(jù)我們在第一步分析的結(jié)果來看，Traffic (400+ requests per second)或者lots of data (3TBs for all urls, 36 GB for all hashes)可能是瓶頸。然后詳細(xì)分析每個(gè)問題，流量可能并沒有什么大問題，我們可能對數(shù)據(jù)更感興趣，接著就可以深入討論數(shù)據(jù)問題了。
第四部：擴(kuò)展抽象設(shè)計(jì)（Scaling Your Abstract Design）
接下來就是詳細(xì)擴(kuò)展你的設(shè)計(jì)來解決這些瓶頸了。這里需要用到的就是一些常用的擴(kuò)展原則，這就需要靠平時(shí)的積累了。
首先，需要了解一些關(guān)于scalability的理論知識。例如，一些基本概念：Vertical scaling、Horizontal scaling、Caching、Load balancing、Database replication、Database partitioning?；蛘哓?fù)載均衡、多用戶、大數(shù)據(jù)的處理方案等。
然后，可以參考High Scalability上介紹的一些有名的公司解決一些棘手提問的方法。并且在看的時(shí)候多留意他們用什么方法解決了什么問題，這些解決方案涉及到的理論方法等。另外，還可以從自己從事的項(xiàng)目中總結(jié)經(jīng)驗(yàn)，遇到的問題，最后采用的解決方案，這些親身經(jīng)歷的事情可能會感觸更深吧。
繼續(xù)回到上面的例子，這里是擴(kuò)展的示例，更多詳情請移步原文觀看視頻解說。
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)
最后：總結(jié)（Summary）
面試的時(shí)候一般第四步還沒有徹底討論完，可能已經(jīng)到時(shí)間了。不過，如果時(shí)間還有富余，可以把上述四步中的具體結(jié)果再總結(jié)一下。無論是遠(yuǎn)程還是現(xiàn)場面試，總結(jié)的時(shí)候把每步結(jié)果都寫下來，不僅反映了你很清晰的條理和總結(jié)能力，還給面試官事后給你寫評價(jià)提供了素材。
下面是原文中對上述四點(diǎn)的總結(jié)：
- 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.
