程序員面試金典, 6/e

蓋爾·拉克曼·麥克道爾（Gayle Laakmann McDowell），CareerCup創始人兼CEO，是一位知名軟件工程師，曾在微軟、蘋果與穀歌任職。早先，她自己是一位十分成功的求職者，通過了微軟、谷歌、亞馬遜、蘋果、IBM、高盛等多家知名企業極其嚴苛的面試過程。工作以後，她又成為一位出色的面試官。在谷歌任職期間，她還是該公司有名的面試官及招聘委員會成員，其間閱人無數，積累了相當豐富的面試經驗。除此書外，還著有《產品經理面試寶典》《金領簡歷：敲開蘋果、微軟、谷歌的大門》。
【譯者簡介】
劉博楠，軟件工程師，畢業於哥倫比亞大學，現居美國紐約，就職於谷歌公司，從事雲計算產品的研發工作，同時在紐約城市大學任兼職講師。對分佈式系統、雲計算、數據庫研發有著濃厚的興趣。對超大規模系統架構設計、流程管理、高可用服務運維等領域也有涉獵。
趙鵬飛，畢業於西安電子科技大學，目前在蔚來汽車做開發工作。熱愛技術，愛好開源，曾為流行開源項目OpenFeign貢獻源碼，近來專注於開源項目Spring及Spring Boot。熱愛算法，一直活躍於leetcode、牛客網等算法網站。
李琳驍，主要從事嵌入式Linux內核/驅動開發，並關注IT、開放源碼和安防監控等領域。業餘時間以技術翻譯為樂，翻譯或參與翻譯了《Linux命令詳解手冊》《編程人生》《編程大師訪談錄》等圖書。
漆犇，畢業於中國地質大學，擁有十餘年軟件開發、測試及流程管理經驗，熱衷翻譯，已出版譯作包括《Linux/Unix設計思想》《金領簡歷：敲開蘋果、微軟、谷歌的大門》等書。

第1章面試流程1

1.1為什麼1

1.1.1錯過了優秀人才是可以的2

1.1.2解決問題的技能很寶貴2

1.1.3基礎數據結構和算法知識很有用2

1.1.4白板讓你專注於重要的事情2

1.1.5但這並不適用於每個人、每家公司、每種場合3

1.2面試問題的來源3

1.3一切都是相對的3

1.4常見問題4

1.4.1面試結束後沒有立即收到回复，我是被拒了嗎4

1.4.2被拒之後我還能重新申請嗎4

第2章面試揭秘5

2.1微軟面試6

2.1.1必備項6

2.1.2獨特之處6

2.2亞馬遜面試6

2.2.1必備項7

2.2.2獨特之處7

2.3谷歌面試7

2.3.1必備項8

2.3.2獨特之處8

2.4蘋果面試8

2.4.1必備項9

2.4.2獨特之處9

2.5 Facebook面試9

2.5.1必備項9

2.5.2獨特之處10

2.6 Palantir面試10

2.6 .1必備項10

2.6.2獨特之處10

第3章特殊情況11

3.1有工作經驗的求職者11

3.2測試人員和軟件開發測試工程師11

3.3產品經理（項目經理） 12

3.4開發主管與部門經理13

3.5創業公司13

3.5.1職位申請14

3.5.2簽證與工作許可14

3.5.3簡歷篩選因素14

3.5.4面試流程14

3.6收購與“人才收購” 14

3.6.1哪些創業公司需要進行併購面試，為什麼14

3.6. 2這些面試有多重要15

3.6.3哪些員工需要面試15

3.6.4如果面試表現不好會怎麼樣15

3.6.5最優秀和最差的員工或許會令你吃驚16

3.6.6被收購方的員工與一般求職者的標準一樣嗎16

3.6.7被收購員工對於收購、人才收購會如何反應16

3.6.8收購後的團隊會經歷什麼16

3.6.9怎樣為你的團隊準備收購面試16

3.7面試官17

3.7.1不要問與本書完全相同的題目17

3.7.2問中等難題或者高難度題17

3.7.3使用多重障礙的題目17

3.7.4使用高難度題目，而不是艱深的基礎知識18

3.7.5避免“嚇人”的問題18

3.7.6提供正面鼓勵19

3.7.7深究行為面試題19

3.7.8輔導求職者19

3.7.9如果求職者想保持安靜，請滿足20

3.7.10了解你的模式：完整性測試、質量測試、專業知識和代理知識20

第4章面試之前22

4.1積累相關經驗22

4.2寫好簡歷23

4.2.1簡歷篇幅長度適中23

4.2.2工作經歷23

4.2.3項目經歷23

4.2.4軟件和編程語言24

4.2.5給母語為非英語的人及國際人士的建議24

4.2.6提防（潛在的）污名24

4.3準備流程圖25

第5章行為面試題28

5.1面試準備清單28

5.1.1你有哪些缺點28

5.1.2你應該問面試官哪些問題28

5.2掌握項目所用的技術29

5.3如何應對29

5.3.1力求具體，切忌自大29

5.3 .2省略細枝末節30

5.3.3多談自己30

5.3.4回答條理清晰30

5.3.5行動是關鍵31

5.3.6故事的意義31

5.4自我介紹32

5.4.1結構32

5.4.2興趣愛好32

5.4. 3展示成功的點點滴滴33

第6章大Ο 34

6.1打個比方34

6.2時間複雜度34

6.2.1大Ο、大θ和大Ω 35

6.2.2最優、最壞和期望情況35

6.3空間複雜度36

6.4刪除常量36

6.5丟棄不重要的項37

6.6多項式算法：加與乘38

6.7分攤時間38

6.8 Log N運行時間39

6.9遞歸的運行時間39

6.10示例和習題40

第7章技術面試題53

7.1準備事項53

7.2必備的基礎知識53

7.2.1核心數據結構、算法及概念53

7.2.2 2的冪表54

7.3解題步驟54

7.4優化和解題技巧1：尋找BUD 58

7.4.1瓶頸59

7.4.2無用功59

7.4.3重複性工作60

7.5優化和解題技巧2：親力親為61

7.6優化和解題技巧3：化繁為簡62

7.7優化和解題技巧4：由淺入深62

7.8優化和解題技巧5：數據結構頭腦風暴法63

7.9可想像的極限運行時間63

7.10處理錯誤答案66

7.11做過的面試題66

7.12面試的“完美”語言67

7.12.1流行度67

7.12.2語言可讀性67

7.12.3潛在問題67

7.12.4冗長67

7.12.5易用性68

7.13好代碼的標準68

7.13.1多多使用數據結構68

7.13.2適當代碼復用69

7.13.3模塊化70

7.13.4靈活性和通用性70

7.13.5錯誤檢查71

7.14不要輕言放棄71

第8章錄用通知及其他注意事項72

8.1如何處理錄用與被拒的情況72

8.1.1回复期限與延長期限72

8.1.2如何拒絕錄用通知72

8.1.3如何處理被拒72

8.2如何評估錄用待遇73

8.2.1薪酬待遇的考量73

8.2.2職業發展73

8.2.3公司穩定性73

8.2.4幸福指數74

8.3錄用談判74

8.4入職須知75

8.4.1制定時間表75

8.4.2打造堅實的人際網絡75

8.4.3向經理尋求幫助75

8.4.4保持面試狀態75

第9章面試題目76

9.1數組與字符串76

9.1.1散列表76

9.1.2 ArrayList與可變長度數組77

9.1.3 StringBuilder 77

9.2鍊錶79

9.2.1創建鍊錶79

9.2.2刪除單向鍊錶中的節點80

9.2.3 “快行指針”技巧80

9.2.4遞歸問題81

9.3棧與隊列82

9.3.1實現一個棧82

9.3.2實現一個隊列83

9.4樹與圖85

9.4.1樹的類型85

9.4.2二叉樹的遍歷87

9.4.3二叉堆（小頂堆與大頂堆） 88

9.4.4單詞查找樹（前序樹） 89

9.4.5圖90

9.4.6圖的搜索91

9.5位操作94

9.5.1手工位操作95

9.5.2位操作原理與技巧95

9.5.3二進制補碼與負數95

9.5.4算術右移與邏輯右移96

9.5.5常見位操作：獲取與設置數位97

9.6數學與邏輯題99

9.6.1素數99

9.6.2概率101

9.6.3大聲說出你的思路102

9.6.4總結規律和模式102

9.6.5略作變通103

9.6.6觸類旁通104

9.7面向對象設計105

9.7.1如何解答105

9.7.2設計模式106

9.8遞歸與動態規劃108

9.8.1解題思路109

9.8.2遞歸與迭代109

9.8.3動態規劃及記憶法109

9.9系統設計與可擴展性114

9.9.1處理問題114

9.9.2循環漸進的設計114

9.9.3逐步構建的方法：循序漸進116

9.9.4關鍵概念116

9.9.5系統設計要考慮的因素118

9.9.6人無完人，系統亦然119

9.9.7實例演示119

9.10排序與查找121

9.10.1常見的排序算法121

9.10.2查找算法124

9.11測試126

9.11.1面試官想考查什麼126

9.11.2測試現實生活中的事物127

9.11.3測試一套軟件127

9.11.4測試一個函數129

9.11.5調試與故障排除129

9.12 C和C++ 131

9.12.1類和集成131

9.12.2構造函數和析構函數131

9.12.3虛函數132

9.12.4虛析構函數133

9.12.5默認值134

9.12.6操作符重載134

9.12.7指針和引用134

9.12.8模板135

9.13 Java 136

9.13.1如何處理137

9.13.2重載與重寫137

9.13.3集合框架138

9.14數據庫139

9.14.1 SQL語法及各類變體139

9.14.2規範化數據庫和非規範化數據庫139

9.14.3 SQL語句140

9.14.4小型數據庫設計141

9.14.5大型數據庫設計142

9.15線程與鎖143

9.15.1 Java線程143

9.15.2同步和鎖145

9.15.3死鎖及死鎖的預防148

9.16中等難題149

9.17高難度題152

第10章題目解法156

10.1數組與字符串156

10.2鍊錶170

10.3棧與隊列186

10.4樹與圖197

10.5位操作229

10.6數學與邏輯題240

10.7面向對象設計254

10.8遞歸與動態規劃286

10.9系統設計與可擴展性313

10.10排序與查找332

10.11測試350

10.12 C和C++ 354

10.13 Java 363

10.14數據庫370

10.15線程與鎖375

10.16中等難題388

10.17高難度題450

第11章進階話題539

11.1實用數學539

11.1.1整數1至N的和540

11.1.2 2的冪的和540

11.1.3對數的底542

11.1.4排列541

11.1.5組合541

11.1.6歸納證明541

11.2拓撲排序542

11.3 Dijkstra算法543

11.4散列表衝突解決方案545

11.4.1使用鍊錶連接數據545

11.4.2使用二叉搜索樹連接數據546

11.4.3使用線性探測進行開放尋址546

11.4.4平方探測和雙重散列546

11.5 Rabin- Karp子串查找546

11.6 AVL樹547

11.6.1性質547

11.6.2插入操作547

11.7紅黑樹548

11.7.1性質549

11.7.2為什麼這樣的樹是平衡的549

11.7.3插入操作549

11.8 MapReduce 551

11.9補充學習內容553

附錄A代碼庫554

附錄B提示560