技術面試題是許多頂尖科技公司面試的主要内容，其中一些難題會令許多面試者望而卻步，但其實這些題是有合理的解決方法的。
7.1 準備事項
多數求職者隻是通讀一遍問題和解法，囫囵吞棗。這好比試圖單憑看問題和解法就想學會微積分。你得動手練習如何解題，單靠死記硬背效果不彰。
就本書的面試題以及你可能遇到的其他題目，請參照以下幾個步驟。
(1) 盡量獨立解題。本書後面有一些提示可供參考，但請盡量不要依賴提示解決問題。許多題目确實難乎其難，但是沒關系，不要怕！此外，解題時還要考慮空間和時間效率。
(2) 在紙上寫代碼。在電腦上程式設計可以享受到文法高亮、代碼完整、調試快速等種種好處，在紙上寫代碼則不然。通過在紙上多多實踐來适應這種情況，并對在紙上編寫、編輯代碼之緩慢習以為常。
(3) 在紙上測試代碼。就是要在紙上寫下一般用例、基本用例和錯誤用例等。面試中就得這麼做，是以最好提前做好準備。
(4) 将代碼照原樣輸入計算機。你也許會犯一大堆錯誤。請整理一份清單，羅列自己犯過的所有錯誤，這樣在真正面試時才能牢記在心。
此外，盡量多做模拟面試。你和朋友可以輪流給對方做模拟面試。雖然你的朋友不見得受過什麼專業訓練，但至少能帶你過一遍代碼或者算法面試題。你也會在當面試官的體驗中，受益良多。
7.2 必備的基礎知識
許多公司關注資料結構和算法面試題，并不是要測試面試者的基礎知識。然而，這些公司卻預設面試者已具備相關的基礎知識。
7.2.1 核心資料結構、算法及概念
大多數面試官都不會問你二叉樹平衡的具體算法或其他複雜算法。老實說，離開學校這麼多年，恐怕他們自己也記不清這些算法了。
一般來說，你隻要掌握基本知識即可。下面這份清單列出了必須掌握的知識。
| 資料結構 | 算法 | 概念 |
|---|---|---|
| 連結清單 | 廣度優先搜尋 | 位操作 |
| 樹、單詞查找樹、圖 | 深度優先搜尋 | 記憶體（堆和棧） |
| 棧和隊列 | 二分查找 | 遞歸 |
| 堆 | 歸并排序 | 動态規劃 |
| 向量/數組清單 | 快排 | 大  |
| 散清單 |
對于上述各項題目，務必掌握它們的具體用法、實作方法、應用場景以及空間和時間複雜度。
一種不錯的方法就是練習如何實作資料結構和算法（先在紙上，然後在電腦上）。你會在這個過程中學到資料結構内部是如何工作的，這對很多面試而言都是不可或缺的。
你錯過上面那段了嗎？千萬不要錯過，這非常重要。如果對上面列出的某個資料結構和算法感覺不能運用自如，就從頭開始練習吧。
其中，散清單是必不可少的一個題目。對這個資料結構，務必要胸有成竹。
7.2.2 2的幂表
下面這張表會在很多涉及可擴充性或者記憶體排序限制等問題上助你一臂之力。盡管不強求你記下來，可是記住總會有用。你至少應該輕車熟路。
| 2的幂 | 準确值（X） | 近似值 | X位元組轉換成MB、GB等 |
|---|---|---|---|
| 7 | 128 | ||
| 8 | 256 | ||
| 10 | 1024 | 一千 | 1 K |
| 16 | 65 536 | 64 K | |
| 20 | 1 048 576 | 一百萬 | 1 MB |
| 30 | 1 073 741 824 | 十億 | 1 GB |
| 32 | 4 294 967 296 | 4 GB | |
| 40 | 1 099 511 627 776 | 一萬億 | 1 TB |
這張表可以拿來做速算。例如，一個将每個32位整數映射成布爾值的向量表可以在一台普通計算機記憶體中放下。那樣的整數有
個。因為每個整數隻占位向量表中的一位，共需要
位（或者
位元組）來存儲該映射表，大約是千兆位元組的一半，普通機器很容易滿足。
在接受網際網路公司的電話面試時，不妨把表放在眼前，也許能派上用場。
7.3 解題步驟
下面的流程圖将教你如何逐漸解決一個問題。要學以緻用。你可以從CrackingTheCodingInterview.com下載下傳這個提綱及更多内容。
接下來我會詳述該流程圖。
面試期待
面試本就困難。如果你無法立刻得出答案，那也沒有關系，這很正常，并不代表什麼。
注意聽面試官的提示。面試官有時熱情洋溢，有時卻意興闌珊。面試官參與程度取決于你的表現、問題的難度以及該面試官的期待和個性。
當你被問到一個問題或者當你在練習時，按下面的步驟完成解題。
7.3.1.1 認真聽
也許你以前聽過這個正常性建議：確定聽清楚題。但我給你的建議不止這一點。
當然了，你首先要保證聽清題，其次弄清楚模棱兩可的地方。
但是我要說的不止如此。
舉個例子，假設一個問題以下列其中一個話題作為開頭，那麼可以合理地認為它給出的所有資訊都并非平白無故的。
“有兩個排序的數組，找到……”
你很可能需要注意到資料是有序的。資料是否有序會導緻最優算法大相徑庭。
“設計一個在伺服器上經常運作的算法……”
在伺服器上/重複運作不同于隻運作一次的算法。也許這意味你可以緩存資料，或者意味着你可以順理成章地對資料集進行預處理。
如果資訊對算法沒影響，那麼面試官不大可能（盡管也不無可能）把它給你。
很多求職者都能準确聽清問題。但是開發算法的時間隻有短短的十來分鐘，以至于解決問題的一些關鍵細節被忽略了。這樣一來無論怎樣都無法優化問題了。
你的第一版算法确實不需要這些資訊。但是如果你陷入瓶頸或者想尋找更優方案，就回頭看看有沒有錯過什麼。
即使把相關資訊寫在白闆上也會對你大有裨益。
7.3.1.2 畫個例圖
畫個例圖能顯著提高你的解題能力，盡管如此，還有如此多的求職者隻是試圖在腦海中解決問題。
當你聽到一道題時，離開椅子去白闆上畫個例圖。
不過畫例圖是有技巧的。首先你需要一個好例子。
通常情況下，以一棵二叉搜尋樹為例，求職者可能會畫如下例圖。
這是個很糟糕的例子。第一，太小，不容易尋找模式。第二，不夠具體，二叉搜尋樹有值。如果那些數字可以幫助你處理這個問題怎麼辦？第三，這實際上是個特殊情況。它不僅是個平衡樹，也是個漂亮、完美的樹，其每個非葉節點都有兩個子節點。特殊情況極具欺騙性，對解題無益。
實際上，你需要設計一個這樣的例子。
- 具體。應使用真實的數字或字元串（如果适用的話）。
- 足夠大。一般的例子都太小了，要加大0.5倍。
- 具有普适性。請務必謹慎，很容易不經意間就畫成特殊的情況。如果你的例子有任何特殊情況（盡管你覺得它可能不是什麼大事），也應該解決這一問題。
盡力做出最好的例子。如果後面發現你的例子不那麼正确，你應該修複它。
7.3.1.3 給出一個蠻力法
一旦完成了例子（其實，你也可以在某些問題中調換7.3.1.2步和7.3.1.3步的順序），就給出一個蠻力法。你的初始算法不怎麼好也沒有關系，這很正常。
一些求職者不想給出蠻力法，是因為他們認為此方法不僅顯而易見而且糟糕透頂。但是事實是：即使對你來說輕而易舉，也未必對所有求職者來說都這樣。你不會想讓面試官認為，即使解出這一簡單算法對你來說也得絞盡腦汁。
初始解法很糟糕，這很正常，不必介懷。先說明該解法的空間和時間複雜度，再開始優化。
7.3.1.4 優化
你一旦有了蠻力法，就應該努力優化該方法。以下技巧就有了用武之地。
(1) 尋找未使用的資訊。你的面試官告訴過你數組是有序的嗎？你如何利用這些資訊？
(2) 換個新例子。很多時候，換個不同的例子會讓你思路暢通，看到問題模式所在。
(3) 嘗試錯誤解法。低效的例子能幫你看清優化的方法，一個錯誤的解法可能會幫助你找到正确的方法。比方說，如果讓你從一個所有值可能都相等的集合中生成一個随機值。一個錯誤的方法可能是直接傳回半随機值。可以傳回任何值，但是可能某些值機率更大，進而思考為什麼解決方案不是完美随機值。你能調整機率嗎？
(4) 權衡時間、空間。有時存儲額外的問題相關資料可能對優化運作時間有益。
(5) 預處理資訊。有辦法重新組織資料（排序等）或者預先計算一些有助于節省時間的值嗎？
(6) 使用散清單。散清單在面試題中用途廣泛，你應該第一個想到它。
(7) 考慮可想象的極限運作時間（詳見7.9節）。
在蠻力法基礎上試試這些技巧，尋找BUD的優化點。
7.3.1.5 梳理
明确了最佳算法後，不要急于寫代碼。花點時間鞏固對該算法的了解。
白闆程式設計很慢，慢得超乎想象。測試、修複亦如此。是以，要盡可能地在一開始就確定思路近乎完美。
梳理你的算法，以了解它需要什麼樣的結構，有什麼變量，何時發生改變。
僞代碼是什麼？如果你更願意寫僞代碼，沒有問題。但是寫的時候要當心。基本的步驟（(1) 通路數組。(2) 找最大值。(3) 堆插入。）或者簡明的邏輯（if, movep < q
. else movep
.）值得一試。但是如果你用簡單的詞語代表q
循環，基本上這段代碼就爛透了，除了代碼寫得快之外一無是處。for
你如果沒有徹底了解要寫什麼，就會在程式設計時舉步維艱，這會導緻你用更長的時間才能完成，并且更容易犯大錯。
7.3.1.6 實作
這下你已經有了一個最優算法并且對所有細節都了如指掌，接下來就是實作算法了。
寫代碼時要從白闆的左上角（要省着點空間）開始。代碼盡量沿水準方向寫（不要寫成一條斜線），否則會亂作一團，并且像Python那樣對空格敏感的語言來說，讀起來會雲裡霧裡，令人困惑。
切記：你隻能寫一小段代碼來證明自己是個優秀的開發人員。是以，每行代碼都至關重要，一定要寫得漂亮。
寫出漂亮代碼意味着你要做到以下幾點。
- 子產品化的代碼。這展現了良好的代碼風格，也會使你解題更為順暢。如果你的算法需要使用一個初始化的矩陣，例如
{{1, 2, 3}, {4, 5, 6}, ...}
initIncrementalMatrix(int size)
- 錯誤檢查。有些面試官很看重這個，但有些對此并不“感冒”。一個好辦法是在這裡加上
todo
- 使用恰到好處的類、結構體。如果需要在函數中傳回一個始末點的清單，可以通過二維數組來實作。當然，更好的辦法是把
StartEndPair
Range
list
- 好的變量名。到處使用單字母變量的代碼不易讀取。這并不是說在恰當場合（比如一個周遊數組的普通
for
i
j
i
j
int i = startOfChild(array)
startChild
然而，長的變量名寫起來也會比較慢。你可以除第一次以外都用縮寫，多數面試官都能同意。比方說你第一次可以使用
startChild
，然後告訴面試官後面你會将其縮寫為
sc
。
評價代碼好壞的标準因面試官、求職者、題目的不同而有所變化。是以隻要專心寫出一手漂亮的代碼即可，盡人事、知天命。
如果發現某些地方需要稍後重構，就和面試官商量一下，看是否值得花時間重構。通常都會得到肯定答複，偶爾不是。
如果覺得一頭霧水（這很常見），就再回頭過一遍。
7.3.1.7 測試
在現實中，不經過測試就不會簽入代碼；在面試中，未經過測試同樣不要“送出”。
測試代碼有兩種辦法：一種聰明的，一種不那麼聰明的。
許多求職者會用最開始的例子來測試代碼。那樣做可能會發現一些bug，但同樣會花很長時間。手動測試很慢。如果設計算法時真的使用了一個大而好的例子，那麼測試時間就會很長，但最後可能隻在代碼末尾發現一些小問題。
你應該嘗試以下方法。
(1) 從概念測試着手。概念測試就是閱讀和分析代碼的每一行。像代碼評審那樣思考，在心中解釋每一行代碼的含義。
(2) 跳着看代碼。重點檢查類似
x = length-2
的行。對于
for
循環，要尤為注意初始化的地方，比如
i = 1
。當你真的去檢查時，就很容易發現小錯誤。
(3) 熱點代碼。如果你程式設計經驗足夠豐富的話，就會知道哪些地方可能出錯。遞歸中的基線條件、整數除法、二叉樹中的空節點、連結清單疊代中的開始和結束，這些要反複檢查才行。
(4) 短小精悍的用例。接下來開始嘗試測試代碼，使用真實、具體的用例。不要使用大而全的例子，比如前面用來開發算法的8元素數組，隻需要使用3到4個元素的數組就夠了。這樣也可以發現相同的bug，但比大的快多了。
(5) 特殊用例。用空值、單個元素、極端情況和其他特殊情況檢測代碼。
發現了bug（很可能會）就要修複。但注意不要貿然修改。仔細斟酌，找出問題所在，找到最佳的修改方案，隻有這樣才能動手。
7.4 優化和解題技巧 1：尋找BUD
這也許是我找到的優化問題最有效的方法了。BUD是以下詞語的首字母縮寫：
- 瓶頸（bottleneck）；
- 無用功 （unnecessary work）；
- 重複性工作 （duplicated work）。
以上是最常見的3個問題，而面試者在優化算法時往往會浪費時間于此。你可以在蠻力法中找找它們的影子。發現一個後，就可以集中精力來解決。
如果這樣仍沒有得到最佳算法，也可以在目前最好的算法中找找這3類優化點。
7.4.1 瓶頸
瓶頸就是算法中拖慢整體運作時間的某部分。通常會以兩種方式出現。
一次性的工作會拖累整個算法。例如，假設你的算法分為兩步，第一步是排序整個數組，第二步是根據屬性找到特定元素。第一步是
，第二步是
。盡管可以把第二步時間優化到
甚至
，但那又有什麼用呢？聊勝于無而已。它不是當務之急，因為
才是瓶頸。除非優化第一步，否則你的算法整體上一直是
。
你有一塊工作不斷重複，比如搜尋。也許你可以把它從
降到
甚至
。這樣就大大加快了整體運作時間。
優化瓶頸，對整體運作時間的影響是立竿見影的。
舉個例子：有一個值都不相同的整數數組，計算兩個數內插補點為的對數。例如，數組谷歌、蘋果、亞馬遜等大廠技術面試真題 ，內插補點{1, 7, 5, 9, 2, 12, 3}
為2，內插補點為2的一共有4對：(1, 3)、(3, 5)、(5, 7)、(7, 9)。谷歌、蘋果、亞馬遜等大廠技術面試真題
用蠻力法就是周遊數組，從第一個元素開始搜尋剩下的元素（即一對中的另一個）。對于每一對，計算內插補點。如果內插補點等于
，計數加一。
該算法的瓶頸在于重複搜尋對數中的另一個。是以，這是接下來優化的重點。
怎麼才能更快地找到正确的另一個？已知
的另一個，即
或
。如果把數組排序，就可以用二分查找來找到另一個，
個元素的話查找的時間就是
。
現在，将算法分為兩步，每一步都用時
。接下來，排序構成新的瓶頸。優化第二步于事無補，因為第一步已經拖慢了整體運作時間。
必須完全丢棄第一步排序數組，隻使用未排序的數組。那如何在未排序的數組中快速查找呢？借助散清單吧。
把數組中所有元素都放到散清單中。然後判斷
或者
是否存在。隻是過一遍散清單，用時為
。
7.4.2 無用功
舉個例子：列印滿足的所有正整數解，其中谷歌、蘋果、亞馬遜等大廠技術面試真題 、谷歌、蘋果、亞馬遜等大廠技術面試真題 、谷歌、蘋果、亞馬遜等大廠技術面試真題 、谷歌、蘋果、亞馬遜等大廠技術面試真題 是1至1000間的整數。谷歌、蘋果、亞馬遜等大廠技術面試真題
用蠻力法來解會有四重
for
循環，如下：
1. n = 1000
2. for a from 1 to n
3. for b from 1 to n
4. for c from 1 to n
5. for d from 1 to n
6. if a3 + b3 == c3 + d3
7. print a, b, c, d
用上面算法疊代
、
、
、
所有可能，然後檢測是否滿足上述表達式。
在找到一個可行解後，就不用繼續檢查
的其他值了。因為
的一次循環中隻有一個值能滿足。是以一旦找到可行解至少應該跳出循環。
1. n = 1000
2. for a from 1 to n
3. for b from 1 to n
4. for c from 1 to n
5. for d from 1 to n
6. if a3 + b3 = c3 + d3
7. print a, b, c, d
8. break // 跳出d循環
雖然該優化對運作時間并無改變，運作時間仍是
，但仍值得一試。
還有其他無用功嗎？答案是肯定的，對于每個
，都可以通過
這個簡單公式得到
。
1. n = 1000
2. for a from 1 to n
3. for b from 1 to n
4. for c from 1 to n
5. d = pow(a3 + b3 - c3, 1/3) // 取整成int
6. if a3 + b3 == c3 + d3 && 0 <= d && d <= n // 驗證結果
7. print a, b, c, d
第6行的
if
語句至關重要，因為第5行每次都會找到一個
的值，但是需要檢查是否是正确的整數值。
這樣一來，運作時間就從
降到了
。
7.4.3 重複性工作
沿用上述問題及蠻力法，這次來找一找有哪些重複性工作。
這個算法本質上周遊所有
對的可能性，然後尋找所有
對的可能性，找到和
對比對的對。
為什麼對于每一對
都要計算所有
對的可能性？隻需一次性建立一個
對清單，然後對于每個
對，都去
清單中尋找比對。想要快速定位
對，對
清單中每個元素，都可以把
對的和當作鍵，
當作值（或者滿足那個和的對清單）插入到散清單。
1. n = 1000
2. for c from 1 to n
3. for d from 1 to n
4. result = c3 + d3
5. append (c, d) to list at value map[result]
6. for a from 1 to n
7. for b from 1 to n
8. result = a3 + b3
9. list = map.get(result)
10. for each pair in list
11. print a, b, pair
實際上，已經有了所有
對的散清單，大可直接使用。不需要再去生成
對。每個
都已在散清單中。
1. n = 1000
2. for c from 1 to n
3. for d from 1 to n
4. result = c<sup>3</sup> + d<sup>3</sup>
5. append (c, d) to list at value map[result]
6.
7. for each result, list in map
8. for each pair1 in list
9. for each pair2 in list
10. print pair1, pair2
它的運作時間是
。
7.5 優化和解題技巧 2：親力親為
第一次遇到如何在排序的數組中尋找某個元素（習得二分查找之前），你可能不會一下子想到：“啊哈！我們可以比較中間值和目标值，然後在剩下的一半中遞歸這個過程。”
然而，如果讓一些沒有計算機科學背景的人在一堆按字母表排序的論文中尋找指定論文，他們可能會用到類似于二分查找的方式。他們估計會說：“天哪，Peter Smith？可能在這堆論文的下面。”然後随機選擇一個中間的（例如i，s，h開頭的）論文，與Peter Smith做比較，接着在剩餘的論文中繼續用這個方法查找。盡管他們不知道二分查找，但可以憑直覺“做出來”。
我們的大腦很有趣。幹巴巴地抛出像“設計一個算法”這樣的題目，人們經常會搞得亂七八糟。但是如果給出一個執行個體，無論是資料（例如數組）還是現實生活中其他的類似物（例如一堆論文），他們就會憑直覺開發出一個很好的算法。
我已經無數次地看到這樣的事發生在求職者身上。他們在計算機上完成的算法奇慢無比，但一旦被要求人工解決同樣問題，立馬幹淨利落地完成。
是以，當你遇到一個問題時，一個好辦法是嘗試在直覺的真執行個體子上憑直覺解決它。通常越大的例子越容易。
舉個例子：給定較小字元串和較大字元串s
，設計一個算法，尋找在較大字元串中較小字元串的所有排列，列印每個排列的位置。b
考慮一下你要怎麼解決這道題。注意排列是字元串的重組，是以
s
中的字元能以任何順序出現在
b
中，但是它們必須是連續的（不被其他字元隔開）。
像大多數求職者一樣，你可能會這麼想：先生成
s
的全排列，然後看它們是否在
b
中。全排列有
種，是以運作時間是
，其中
是
s
的長度，
是
b
的長度。
這樣是可行的，但實在慢得太離譜了。實際上該算法比指數級的算法還要糟糕透頂。如果
s
有14個字元，那麼會有超過870億個全排列。
s
每增加一個字元，全排列就會增加15倍。天哪！
換種不同的方式，就可以輕而易舉地開發出一個還不錯的算法。參考如下例子：
s：abbc
b：cbabadcbbabbcbabaabccbabc
b
中
s
的全排列在哪兒？不要管如何做，找到它們就行。很簡單的，12歲的小孩子都能做到！
（真的，趕緊去找，我等你。）
我已經在每個全排列下面畫了線。
s: abbc
b: cbabadcbbabbcbabaabccbabc
———— ———— ————
———— ———— ————
————
你找到了嗎？怎麼做的？
很少有人——即使之前提出
算法的人——真的去生成
abbc
的全排列，再去
b
中逐個尋找。幾乎所有人都采用了如下兩種方式（非常相似）之一。
(1) 周遊
b
，檢視4個字元（因為
s
中隻有4個字元）的滑動視窗。逐一檢查視窗是否是
s
的一個全排列。
(2) 周遊
b
。每次發現一個字元在
s
中時，就去檢查它往後的4個（包括它）字元是否屬于
s
的全排列。
取決于“是否是一個全排列”的具體實作方式，你得到的運作時可能是
、
或者
。盡管這些都不是最優算法（包含
算法），但已經比我們之前的好太多。
解題時，試試這個方法。使用一個大而好的例子，直覺地手動解決這個特定例子。然後複盤，思考你是如何解決它的。反向設計算法。
重點留意你憑直覺或不經意間做的任何“優化”。例如，解題時你可能會跳過以
d
開頭的視窗，因為
d
不在
abbc
中。這是你靠大腦做出的一個優化，在設計算法時也應該留意到。
7.6 優化和解題技巧 3：化繁為簡
我們通過簡化來實作一個由多步驟構成的方法。首先，可以簡化或者調整限制，比如資料類型。這樣一來，就可以解決簡化後的問題了。最後，調整這個算法，讓它适應更為複雜的情況。
舉個例子：可以通過從雜志上剪下詞語拼湊成句來完成一封邀請函。如何分辨一封邀請函（以字元串表示）是否可以從給定雜志（字元串）中擷取呢？
為了簡化問題，可以把從雜志上剪下詞語改為剪下字元。
通過建立一個數組并計數字元串，可以解決邀請函的字元串簡化版問題，其中數組中的每一位對應一個字母。首先計算每個字元在邀請函中出現的次數，然後周遊雜志檢視是否能滿足。
推導出這個算法，意味着我們做了類似的工作。不同的是，這次不是建立一個字元數組來計數，而是建立一個單詞映射頻率的散清單。
7.7 優化和解題技巧 4：由淺入深
我們可以由淺入深，首先解決一個基本情況（例如，
），然後嘗試從這裡開始建構。遇到更複雜或者有趣的情況（通常是
或者
）時，嘗試使用之前的方法解決。
舉個例子：設計一個算法列印出字元串的所有排列組合。簡單起見，假設所有字元均不相同。
思考一個測試字元串
abcdefg
。
用例 "a" --> {"a"}
用例 "ab" --> {"ab", "ba"}
用例 "abc" --> ?
這是第一個“有趣”的情況。如果已經有了
P("ab")
的答案，如何得到
P("abc")
的答案呢？已知可選的字母是
c
，是以可以在每種可能中插入
c
，即如下模式。
P("abc") = 把"c"插入到 P("ab")中的所有字元串的所有位置
P("abc") = 把"c"插入到{"ab","ba"}中的所有字元串的所有位置
P("abc") = 合并({"cab", "acb", "abc"}, {"cba", "bca", bac"})
P("abc") = {"cab", "acb", "abc", "cba", "bca", bac"}
了解了這個模式後，就可以寫個差不多的遞歸算法了。通過“截斷末尾字元”的方式，可以生成
s1...sn
字元串的所有組合。做法很簡單，首先生成字元串
s1...sn-1
的所有組合，然後周遊所有組合，每個字元串的每個位置都插入
sn
得到新的字元串。
這種由基礎例子逐漸推導的方法通常會得到一個遞歸算法。
7.8 優化和解題技巧 5：資料結構頭腦風暴法
這種方法很取巧但奏效。我們可以簡單過一遍所有的資料結構，一個個地試。這種方法之是以有效在于，一旦資料結構（比方說樹）選對了，解題可能就簡單了，手到擒來。
舉個例子：随機産生數字并放入（動态）數組。你怎麼記錄它每一步的中間值？
應用資料結構頭腦風暴法的過程可能如下所示。
- 連結清單？可能不行。連結清單一般不擅長随機通路和排序數字。
- 數組？也許可以，但已經有一個數組了。你能設法保持元素的有序嗎？這樣可能代價巨大。可以先放一放，如果後面需要了再考慮一試。
- 二叉樹？貌似可以，因為二叉樹的看家本領就是排序。實際上，如果這棵二叉搜尋樹是完全平衡二叉搜尋樹的話，頂節點可能就是中間值。但要注意的是，如果數字個數是偶數，中值實際上是中間兩個數的平均值，畢竟這兩個數不能都在頂節點上。該算法可行，但可稍後再考慮。
- 堆？堆對于基本排序和儲存最大值、最小值手到擒來。如果你有兩個堆，事情就有意思了。你可以分别儲存元素中大的一半和小的一半。更大的一半資料儲存在最小堆，是以這較大的一半中最小的元素在根節點。而更小的一半資料儲存在最大堆，是以這較小的一半中最大的元素也在根節點。有了這些資料結構，就得到了所有可能的中值元素。如果兩個堆的大小不一緻，則可以通過從一個堆彈出元素插入到另一個堆實作快速“平衡”。
總的來說，你解決過的問題越多，就越擅于選擇出合适的資料結構。不僅如此，你的直覺還會變得更加敏銳，能判斷出哪種方法最為行之有效。
7.9 可想象的極限運作時間
考慮到可想象的極限運作時間（BCR），可能對解決某些問題大有裨益。
可想象的極限運作時間，按字面意思了解就是，關于某個問題的解決，你可以想象出的運作時間的極限。你可以輕而易舉地證明，BCR是無法超越的。
比方說，假設你想計算兩個數組（長度分别為
、
）共有元素的個數，會立馬想到用時不可能超過
，因為必須要通路每個數組中的所有元素，是以
就是可想象的極限運作時間。
或者，假設你想列印數組中所有成對值。你當然明白用時不可能超過
，因為有
對需要列印。
不過還要注意。假設面試官要求你在一個數組中（假定所有元素均不同）找到所有和為
的對。一些對可想象的極限運作時間概念一知半解的求職者可能會說BCR是
，理由是不得不通路
對。
這種說法大錯特錯。僅僅因為你想要所有和為特定值的對，并不意味着必須通路所有對。事實上根本不需要。
可想象的極限運作時間與最佳運作時間（best case runtime）有什麼關系呢？毫不相幹！可想象的極限運作時間是針對一個問題而言，在很大程度上是一個輸入輸出的函數，和特定的算法并無關系。事實上，如果計算可想象的極限運作時間時還要考慮具體用到哪個算法，那就很可能做錯了。最佳運作時間是針對具體算法（通常是一個毫無意義的值）的。
注意，可想象的極限運作時間不一定可以實作。它的意義在于告訴你用時不會超過該時間。
舉例說明BCR的用法
問題：找到兩個排序數組中相同元素的個數，這兩個數組長度相同，且每個數組中元素都不同。
從如下這個經典例子着手，在共同元素下标注下劃線。
A: 13 27 35 40 49 55 59
B: 17 35 39 40 55 58 60
解出這道題使用的是蠻力法，即對于
A
中的每個元素都去
B
中搜尋。這需要花費
的時間，因為對于
A
中的每個元素（共
個）都需要在
B
中做
的搜尋。
BCR為
，因為我們知道每個元素至少通路一次，一共
個元素。如果跳過一個元素，那麼這個元素是否有相同的值會影響最後的結果。例如，如果從沒有通路過
B
中的最後一個元素，那麼把60改成59，結果就不對了。
回到正題。現在有一個
的算法，我們想要更好地優化該算法，但不一定要像
那樣快。
Brute Force: O(N2)
Optimal Algorithm: ?
BCR: O(N)
與
之間的最優算法是什麼？有許多，準确地講，有無窮無盡。理論上可以有個算法是
。然而，無論是在面試還是現實中，運作時間都不太可能是這樣。
請記住這個問題，因為它在面試中淘汰了很多人。運作時間不是一個多選題。雖然常見的運作時間有、谷歌、蘋果、亞馬遜等大廠技術面試真題 、谷歌、蘋果、亞馬遜等大廠技術面試真題 、谷歌、蘋果、亞馬遜等大廠技術面試真題 或者谷歌、蘋果、亞馬遜等大廠技術面試真題 ，但你不該直接假設某個問題的運作時間是多少而不考慮推導的過程。事實上，當你對運作時間是多少百思不解時，不妨猜一猜。這時你最有可能遇到一個不太明顯、不太常見的運作時間。也許是谷歌、蘋果、亞馬遜等大廠技術面試真題 ，谷歌、蘋果、亞馬遜等大廠技術面試真題 是數組的大小，谷歌、蘋果、亞馬遜等大廠技術面試真題 是數值對的個數。合理推導，不要隻靠猜。谷歌、蘋果、亞馬遜等大廠技術面試真題
最有可能的是，我們正努力推導出
或者
算法。這說明什麼呢？
如果目前算法的運作時間是
，那麼想得到
或者
可能意味着要把第二個
優化成
或者
。
這是BCR的一大益處，我們可以通過運作時間得到關于優化方向的啟示。
第二個
來自于搜尋。已知數組是排序的，可以用快于
的時間在排序的數組中搜尋嗎？
當然可以了，用二分查找在一個排序的數組中尋找一個元素的運作時間是
。
現在我們把算法優化為
。
Brute Force: O(N2)
Improved Algorithm: O(N log N)
Optimal Algorithm: ?
BCR: O(N)
還能繼續優化嗎？繼續優化意味着把
縮短為
。
通常情況下，二分查找在排序數組中的最快運作時間是
。但這次不是正常情況，我們一直在重複搜尋。
BCR告訴我們，解出這個算法的最快運作時間為
。是以，我們所做的任何
的工作都是“免費的”，不會影響到運作時間。
重讀7.3.1節關于優化的技巧，是否有一些可以派上用場呢？
一個技巧是預計算或者預處理。任何
時間内的預處理都是“免費的”。這不會影響運作時間。
這又是BCR的一大益處。任何你所做的不超過或者等于BCR的工作都是“免費的”，從這個意義上來說，對運作時間并無影響。你可能最終會将此剔除，但是目前不是當務之急。
重中之重仍在于将搜尋由
減少為
。任何
或者不超過
時間内的預計算都是“免費的”。
是以，可以把
B
中所有資料都放入散清單，它的運作時間是
，然後隻需要周遊
A
，檢視每個元素是否在散清單中。查找（搜尋）時間是
，是以總的運作時間是
。
假設面試官問了一個讓我們坐立不安的問題：還能繼續優化嗎？
答案是不可以，這裡指運作時間。我們已經實作了最快的運作時間，是以沒辦法繼續優化大
時間，倒可以嘗試優化空間複雜度。
這是BCR的另一大益處。它告訴我們運作時間優化的極限，我們到這兒就該調轉槍頭，開始優化空間複雜度了。
事實上，就算面試官不主動要求，我們也應該對算法抱有疑問。就算不存儲資料，也可以精确地獲得相同的運作時間。那麼為什麼面試官給出了排序的數組？并非不尋常，隻是有些奇怪罷了。
回到我們的例子：
A: 13 27 35 40 49 55 59
B: 17 35 39 40 55 58 60
要找有如下特征的算法。
- 占用空間為 （或許是）。現在已經有了空間為
谷歌、蘋果、亞馬遜等大廠技術面試真題 、時間最優的算法。如果想使用更少的其他空間，這可能意味着沒有其他空間。是以，得丢棄散清單。 谷歌、蘋果、亞馬遜等大廠技術面試真題 - 占用時間為 （或許是）。我們期望最少也要和目前的一樣，該時間是最優時間，不可超越。
谷歌、蘋果、亞馬遜等大廠技術面試真題 - 使用給定的條件，數組有序。
不使用其他空間的最佳算法是二分查找。想一想怎麼優化它。試着過一遍整個算法。
(1) 用二分查找在
B
中找
A[0] = 13
。沒找到。
(2) 用二分查找在
B
中找
A[1] = 27
。沒找到。
(3) 用二分查找在
B
中找
A[2] = 35
。在
B[1]
中找到。
(4) 用二分查找在
B
中找
A[3] = 40
。在
B[5]
中找到。
(5) 用二分查找在
B
中找
A[4] = 49
。沒找到。
(6) ……
想想BUD。搜尋是瓶頸。整個過程有多餘或者重複性工作嗎？
搜尋
A[3] = 40
不需要搜尋整個
B
。在
B[1]
中已找到35，是以40不可能在35前面。
每次二分查找都應該從上次終止點的左邊開始。
實際上，根本不需要二分查找，大可直接借助線性搜尋。隻要在
B
中的線性搜尋每次都從上次終止的左邊出發，就知道将要用線性時間進行搜尋。
(1) 在
B
中線性搜尋
A[0] = 13
，開始于
B[0] = 17
，結束于
B[0] = 17
。未找到。
(2) 在
B
中線性搜尋
A[1] = 27
，開始于
B[0] = 17
，結束于
B[1] = 35
。未找到。
(3) 在
B
中線性搜尋
A[2] = 35
，開始于
B[1] = 35
，結束于
B[1] = 35
。找到。
(4) 在
B
中線性搜尋
A[3] = 40
，開始于
B[2] = 39
，結束于
B[3] = 40
。找到。
(5) 在
B
中線性搜尋
A[4] = 49
，開始于
B[3] = 40
，結束于
B[4] = 55
。找到。
(6) ……
以上算法與合并排序數組如出一轍。該算法的運作時間為
，空間為
。
現在同時達到了BCR和最小的空間占用，這已經是極限了。
這是另一個使用BCR的方式。如果達到了BCR并且其他空間為，那麼不論是大谷歌、蘋果、亞馬遜等大廠技術面試真題 時間還是空間都已經無法優化。谷歌、蘋果、亞馬遜等大廠技術面試真題
BCR不是一個真正的算法概念，也無法在算法教材中找到其身影。但我個人覺得其大有用處，不管是在我自己解題時，還是在指導别人解題時。
如果很難掌握它，先確定你已經了解了大
時間的概念。你要做到運用自如。一旦你掌握了，弄懂BCR不過是小菜一碟。
7.10 處理錯誤答案
流傳最廣、危害最大的謠言就是，求職者必須答對每個問題。這種說法并不全對。
首先，面試的回答不應該簡單分為“對”或“不對”。當我評價一個人在面試中的表現時，從不會想：“他答對了多少題？”評價不是非黑即白。相反地，評價應該基于最終解法有多理想，解題花了多長時間，需要多少提示，代碼有多幹淨。這些才是關鍵。
其次，評價面試表現時，要和其他的候選人做對比。例如，如果你優化一個問題需要15分鐘，别人解決一個更容易的問題隻需要5分鐘，那麼他就比你表現好嗎？也許是，也許不是。如果給你一個顯而易見的問題，面試官可能會希望你幹淨利落地給出最優解法。但是如果是難題，那麼犯些錯也是在意料之中的。
最後，許多或者絕大多數的問題都不簡單，就算一個出類拔萃的求職者也很難立刻給出最優算法。通常來說，對于我提出的一些問題，厲害的求職者也要20到30分鐘才能解出。
我在谷歌評估過成千上萬份求職者的資訊，也隻看到過一個求職者完美無缺地通過了面試。其他人，包括收到錄用通知的人，都或多或少犯過錯。
7.11 做過的面試題
如果你曾見過某個面試題，要提前說明。面試官問你這些問題是為了評估你解決問題的能力。如果你已經知道某個題的答案了，他們就無法準确無誤地評估你的水準了。
此外，如果你對自己見過這道題諱莫如深，面試官還可能會發現你為人不誠實。反過來說，如果你坦白了這一點，就會給面試官留下誠實的好印象。
7.12 面試的“完美”語言
在很多頂級公司，面試官并不在乎你用什麼語言。相比之下，他們更在乎你解決問題的能力。
不過，也有些公司比較關注某種語言，樂于看到你是如何得心應手地使用該語言編寫代碼的。
如果你可以任意選擇語言的話，就選最為得心應手的。
話雖如此，如果你擅長幾種語言，就将以下幾點牢記于心。
7.12.1 流行度
這一點不強求。但是若面試官知道你所使用的語言，可能是最為理想的。從這點上講，更流行的語言可能更為合适。
7.12.2 語言可讀性
即使面試官不知道你所用的語言，他們也希望能對該語言有個大緻了解。一些語言的可讀性天生就優于其他語言，因為它們與其他語言有相似之處。
舉個例子，Java很容易了解，即使沒有用過它的人也能看懂。絕大多數人都用過與Java文法類似的語言，比如C和C++。
然而，像Scala和Objective C這樣的語言，其文法就大不相同了。
7.12.3 潛在問題
使用某些語言會帶來潛在的問題。例如，使用C++就意味着除了代碼中常見的bug，還存在記憶體管理和指針的問題。
7.12.4 冗長
有些語言更為冗長煩瑣。Java就是一個例子，與Python相比，該語言極為煩瑣。通過比較以下代碼就一目了然了。
Python：
1. dict = {"left": 1, "right": 2, "top": 3, "bottom": 4};
Java：
1. HashMap<String, Integer> dict = new HashMap<String, Integer>().
2. dict.put("left", 1);
3. dict.put("right", 2);
4. dict.put("top", 3);
5. dict.put("bottom", 4);
可以通過縮寫使Java更為簡潔。比如一個求職者可以在白闆上這樣寫：
1. HM<S, I> dict = new HM<S, I>().
2. dict.put("left", 1);
3. ... "right", 2
4. ... "top", 3
5. ... "bottom", 4
你需要解釋這些縮寫，但絕大多數面試官并不在意。
7.12.5 易用性
有些語言使用起來更為容易。例如，使用Python可以輕而易舉地讓一個函數傳回多個值。但是如果使用Java，就還需要一個新的類。語言的易用性可能對解決某些問題大有裨益。
與上述類似，可以通過縮寫或者實際上不存在的假設方法讓語言更易使用。例如，如果一種語言提供了矩陣轉置的方法而另一種語言未提供，也并不一定要選第一種語言（如果面試題需要那個函數的話），可以假設另一種語言也有類似的方法。
7.13 好代碼的标準
到目前為止，你可能知道雇主想看到你寫出一手“漂亮的、幹淨的”代碼。但具體的标準是什麼呢？在面試中又如何展現呢？
一般來講，好代碼應符合以下标準。
- 正确：對于預期輸入和非預期輸入都能正确運作。
- 高效：代碼在時間與空間上應盡可能高效，“高效”不單單指漸近線（大 ）的高效，還指實際、現實生活中的高效，也就是說，計算大
谷歌、蘋果、亞馬遜等大廠技術面試真題 時會放棄的常量，在現實生活中可能至關重要。谷歌、蘋果、亞馬遜等大廠技術面試真題 - 簡潔：能用10行代碼解決的問題就不要用100行，開發者應竭盡全力幹淨利落地編寫代碼。
- 可讀性：其他開發者要能看懂你的代碼，能了解代碼的功能以及實作方法。易讀的代碼在必要時有注釋，但其實作方法一目了然。這意味着，你寫出的花哨代碼，比如包含一組複雜的比特位移動，不一定就是好代碼。
- 可維護性：代碼應能合理适應産品在生命周期中的變化，對初始和後來開發者而言，都應易于維護。
追求這些需要掌握好平衡。比如，有時犧牲一定的效率來提高可維護性就是明智之舉，反之亦然。
在面試中寫代碼時應該考慮到這些。以下内容更為具體地闡述了好代碼的标準。
7.13.1 多多使用資料結構
假設讓你寫一個函數，把兩個單獨的數學表達式相加，形如
（其中系數和指數可以為任意正實數或負實數），即該表達式是由一系列項組成，每個項都是一個常數乘以一個指數。面試官還補充說，不希望你解析字元串，但你可以使用任何資料結構。
這有幾種不同的實作方式。
7.13.1.1 糟糕透頂的實作方式
一個糟糕透頂的實作方式是把表達式放在一個
double
的數組中，第
個元素對應表達式中
項的系數。這個資料結構的問題在于，不支援指數為負數或非整數的表達式，還要求1000個元素大小的數組來存儲表達式
。
1. int[] sum(double[] expr1, double[] expr2) {
2. ...
3. }
7.13.1.2 勉強湊合的實作方式
稍差的方案是用兩個數組分别儲存系數和指數。用這種方法，表達式的每一項都有序儲存，但能“比對”。第
項就表示為
oefficients[i]*xexponents[i]
。
對于這種實作方式，如果
coefficients[p] = k
并且
exponents[p] = m
，那麼第
項就是
。雖然這樣沒有了上一種方式的限制，但仍然顯得雜亂無章。一個表達式卻需要使用兩個數組。如果兩個數組長度不同，表達式可能有“未定義”的值。不僅如此，傳回也讓人不勝其煩，因為要傳回兩個數組。
1. ??? sum(double[] coeffs1, double[] expon1, double[] coeffs2, double[] expon2) {
2. ...
3. }
7.13.1.3 優美的實作方式
一個好的實作方式就是為這個問題中的表達式設計資料結構。
1. class ExprTerm {
2. double coefficient;
3. double exponent;
4. }
5.
6. ExprTerm[] sum(ExprTerm[] expr1, ExprTerm[] expr2) {
7. ...
8. }
有些人可能認為甚至聲稱，這是“過度優化”。不管是不是，也不管你有沒有覺得這是過度優化，關鍵在于上面的代碼展現了你在思考如何設計代碼，而不是以最快速度将一些資料東拼西湊。
7.13.2 适當代碼複用
假設讓你寫一個函數來檢查是否一個二進制的值（以字元串表示）等于用字元串表示的一個十六進制數。
解決該問題的一種簡單方法就是複用代碼。
1. boolean compareBinToHex(String binary, String hex) {
2. int n1 = convertFromBase(binary, 2);
3. int n2 = convertFromBase(hex, 16);
4. if (n1 < 0 || n2 < 0) {
5. return false;
6. }
7. return n1 == n2;
8. }
9.
10. int convertFromBase(String number, int base) {
11. if (base < 2 || (base > 10 && base != 16)) return -1;
12. int value = 0;
13. for (int i = number.length() - 1; i >= 0; i--) {
14. int digit = digitToValue(number.charAt(i));
15. if (digit < 0 || digit >= base) {
16. return -1;
17. }
18. int exp = number.length() - 1 - i;
19. value += digit * Math.pow(base, exp);
20. }
21. return value;
22. }
23.
24. int digitToValue(char c) { ... }
可以單獨實作二進制轉換和十六進制轉換的代碼，但這隻會讓代碼難寫且難以維護。不如寫一個
convertFromBase
方法和
digitToValue
方法，然後複用代碼。
7.13.3 子產品化
編寫子產品化的代碼時要把獨立代碼塊放到各自的方法中。這有助于提高代碼的可維護性、可讀性和可測試性。
想象你正在寫一個交換數組中最小數和最大數的代碼，可以用如下方法完成。
1. void swapMinMax(int[] array) {
2. int minIndex = 0;
3. for (int i = 1; i < array.length; i++) {
4. if (array[i] < array[minIndex]) {
5. minIndex = i;
6. }
7. }
8.
9. int maxIndex = 0;
10. for (int i = 1; i < array.length; i++) {
11. if (array[i] > array[maxIndex]) {
12. maxIndex = i;
13. }
14. }
15.
16. int temp = array[minIndex];
17. array[minIndex] = array[maxIndex];
18. array[maxIndex] = temp;
19. }
或者你也可以把相對獨立的代碼塊封裝成方法，這樣寫出的代碼更為子產品化。
1. void swapMinMaxBetter(int[] array) {
2. int minIndex = getMinIndex(array);
3. int maxIndex = getMaxIndex(array);
4. swap(array, minIndex, maxIndex);
5. }
6.
7. int getMinIndex(int[] array) { ... }
8. int getMaxIndex(int[] array) { ... }
9. void swap(int[] array, int m, int n) { ... }
雖然非子產品化的代碼也不算糟糕透頂，但是子產品化的好處是易于測試，因為每個元件都可以單獨測試。随着代碼越來越複雜，代碼的子產品化也愈加重要，這将使代碼更易維護和閱讀。面試官想在面試中看到你能展示這些技能。
7.13.4 靈活性和通用性
你的面試官要求你寫代碼來檢查一個典型的井字棋是否有個赢家，并不意味着你必須要假定是一個3×3的棋盤。為什麼不把代碼寫得更為通用一些，實作成
的棋盤呢？
把代碼寫得靈活、通用，也許意味着可以通過用變量替換寫死值或者使用模闆、泛型來解決問題。如果可以的話，應該把代碼寫得更為通用。
當然，凡事無絕對。如果一個解決方案對于一般情況而言顯得太過複雜，并且不合時宜，那麼實作簡單預期的情況可能更好。
7.13.5 錯誤檢查
一個謹慎的程式員是不會對輸入做任何假設的，而是會通過
ASSERT
和
if
語句驗證輸入。
一個例子就是之前把數字從
進制（比如二進制或十六進制）表示轉換成一個整數。
1. int convertFromBase(String number, int base) {
2. if (base < 2 || (base > 10 && base != 16)) return -1;
3. int value = 0;
4. for (int i = number.length() - 1; i >= 0; i--) {
5. int digit = digitToValue(number.charAt(i));
6. if (digit < 0 || digit >= base) {
7. return -1;
8. }
9. int exp = number.length() - 1 - i;
10. value += digit * Math.pow(base, exp);
11. }
12. return value;
13. }
在第2行，檢查進制數是否有效（假設進制大于10時，除了16以外，沒有标準的字元串表示）。在第6行，又做了另一個錯誤檢查以確定每個數字都在允許範圍内。
像這樣的檢查在生産代碼中至關重要，也就是說，面試中同樣重要。
不過，寫這樣的錯誤檢查會很枯燥無味，還會浪費寶貴的面試時間。關鍵是，要向面試官指出你會寫錯誤檢查。如果錯誤檢查不是一個簡單的
if
語句能解決的，最好給錯誤檢查留有空間，告訴面試官等完成其餘代碼後還會傳回來寫錯誤檢查。
7.14 不要輕言放棄
面試題有時會讓人不得要領，但這隻是面試官的測試手段。直面挑戰還是知難而退？不畏艱險，奮勇向前，這一點至關重要。總而言之，切記面試不是一蹴而就的。遇到攔路虎本就在意料之中。
還有一個加分項：表現出解決難題的滿腔熱情。
本文摘自《程式員面試金典（第6版）》