程序員面試金典（第6版·修訂版）
[美]蓋爾·拉克曼·麥克道爾（Gayle Laakmann McDowell）
商品描述
本書是原谷歌資深面試官的經驗之作，緊扣程序員面試環節，系統而詳盡地介紹了程序員要為面試做哪些準備以及如何應對面試。主要內容涉及面試的流程解析、面試準備工作，以及多家知名公司的面試題目及詳解。修訂版特別結合國內科技公司的近況，修訂了上一版中的一些問題，增添了國內科技公司的面試流程與註意事項。面試題目方面結合近年國內科技公司的考查重點，整合了原有的內容，圍繞考核知識點精選了 100 多道題目，詳細講解了相關的算法策略。
本書適合程序開發人員和想要瞭解相關內容的學生閱讀。
作者簡介
盖尔·拉克曼·麦克道尔，CareerCup创立人兼CEO，是一位软件工程师，曾在微软、苹果与谷歌任职。她曾经顺利通过了微软、谷歌、苹果、IBM、高盛等多家名企极其严苛的面试过程，工作以后，她又成为一位出色的面试官，在谷歌任职期间，她还是谷歌招聘委员会成员，积累了相当丰富的面试经验。除此书外，还著有《产品经理面试宝典》《金领简历：敲开苹果、微软、谷歌的大门》。
目錄大綱
第 一部分 求職準備 全面瞭解
第 1 章 面試之前 1
1.1 積累編程經驗 1
1.2 寫好簡歷 2
1.2.1 簡歷篇幅長度適中 2
1.2.2 工作經歷 2
1.2.3 項目經歷 2
1.2.4 軟件和編程語言 3
1.2.5 提防（潛在的）污名 3
第 2 章 面試的流程 4
2.1 面試準備清單 4
2.1.1 你有哪些缺點 4
2.1.2 你應該問面試官哪些問題 4
2.2 掌握項目所用的技術 5
2.3 如何應對面試中的提問 5
2.3.1 正面應答，避免自大 5
2.3.2 省略細枝末節 6
2.3.3 多談自己 6
2.3.4 回答條理清晰 6
2.4 自我介紹 7
2.4.1 結構 7
2.4.2 展示成功的點點滴滴 8
2.5 面試流程 8
2.5.1 國內企業的面試流程 9
2.5.2 國際企業面試的流程 11
2.6 面試成績 13
第 3 章 技術面試題 14
3.1 準備事項 14
3.2 基礎知識 14
3.2.1 核心數據結構、算法及概念 14
3.2.2 2 的冪表 15
3.3 解題步驟 15
3.3.1 認真聽 16
3.3.2 畫個例圖 17
3.3.3 給出一個蠻力法 17
3.3.4 優化 17
3.3.5 梳理 18
3.3.6 實現 18
3.3.7 測試 19
3.4 優化和解題技巧 19
3.4.1 尋找 BUD 19
3.4.2 親力親為 22
3.4.3 化繁為簡 23
3.4.4 由淺入深 23
3.4.5 數據結構頭腦風暴法 24
3.5 可想象的極限運行時間 24
3.6 處理錯誤答案 27
3.7 做過的面試題 27
3.8 面試的“完美”語言 28
3.9 好代碼的標準 29
第二部分 技術面試題目中的基礎知識
第 4 章 大 O 33
4.1 時間復雜度 33
4.2 空間復雜度 35
4.3 刪除常量 35
4.4 丟棄不重要的項 36
4.5 多項式算法：加與乘 37
4.6 分攤時間 37
4.7 log N 運行時間 38
4.8 遞歸的運行時間 38
4.9 例題分析 39
第 5 章 數組與字符串 52
5.1 散列表 52
5.2 ArrayList 與可變長度數組 53
5.3 StringBuilder 53
第 6 章 鏈表 55
6.1 創建鏈表 55
6.2 刪除單向鏈表中的節點 56
6.3 “快行指針”技巧 56
6.4 遞歸問題 56
第 7 章 棧與隊列 57
7.1 實現一個棧 57
7.2 實現一個隊列 58
第 8 章 樹與圖 60
8.1 樹的類型 60
8.1.1 樹與二叉樹 60
8.1.2 二叉樹與二叉搜索樹 61
8.1.3 平衡與不平衡 61
8.1.4 完整二叉樹 61
8.1.5 滿二叉樹 62
8.1.6 完美二叉樹 62
8.2 二叉樹的遍歷 62
8.3 二叉堆（小頂堆與大頂堆） 63
8.4 單詞查找樹（前序樹） 64
8.5 圖 65
8.5.1 鄰接鏈表法 65
8.5.2 鄰接矩陣法 66
8.6 圖的搜索 66
8.6.1 深度優先搜索 67
8.6.2 廣度優先搜索 67
8.6.3 雙向搜索 68
第 9 章 位操作 69
9.1 手工位操作 69
9.2 位操作原理與技巧 69
9.3 二進制補碼與負數 70
9.4 算術右移與邏輯右移 70
9.5 常見位操作：獲取與設置數位 71
第 10 章 數學與邏輯題 73
10.1 素數 73
10.2 概率 75
10.3 總結規律和模式 76
第 11 章 面向對象設計 78
11.1 如何解答 78
11.2 設計模式 79
11.2.1 單例設計模式 79
11.2.2 工廠方法設計模式 79
第 12 章 遞歸與動態規劃 81
12.1 解題思路 81
12.2 遞歸與迭代 81
12.3 動態規劃及記憶法 82
第 13 章 系統設計與可擴展性 86
13.1 處理問題 86
13.2 循環漸進的設計 87
13.3 逐步構建的方法：循序漸進 88
13.4 關鍵概念 88
13.5 系統設計要考慮的因素 90
13.6 實例演示 91
第 14 章 排序與查找 93
14.1 常見的排序算法 93
14.2 查找算法 95
第 15 章 數據庫 97
15.1 SQL 語法及各類變體 97
15.2 規範化數據庫和反規範化數據庫 97
15.3 SQL 語句 97
15.4 小型數據庫設計 99
15.5 大型數據庫設計 100
第 16 章 C 和 C++ 101
16.1 類和繼承 101
16.2 構造函數和析構函數 101
16.3 虛函數102
16.4 虛析構函數 103
16.5 默認值104
16.6 操作符重載 104
16.7 指針和引用 104
16.8 模板 105
第 17 章 Java 107
17.1 如何處理 107
17.2 重載與重寫 107
17.3 集合框架 108
第 18 章 線程與鎖 110
18.1 Java 線程 110
18.2 同步和鎖 112
18.3 死鎖及死鎖的預防 114
第 19 章 測試 116
19.1 面試官想考查什麽 116
19.2 測試現實生活中的事物 116
19.3 測試一套軟件 117
19.4 測試一個函數 119
19.5 調試與故障排除 119
第三部分 經典題型 輕松拿捏
第 20 章 數組與字符串 121
20.1 判定字符是否唯一 121
20.2 URL 化 122
20.3 迴文串排列 123
20.4 字符串壓縮 125
第 21 章 鏈表 128
21.1 返回倒數第 k 個節點 128
21.2 鏈表求和 130
21.3 鏈表相交 132
21.4 環路檢測 135
第 22 章 棧與隊列 138
22.1 三合一 138
22.2 化棧為隊 142
22.3 棧排序 143
第 23 章 樹與圖 145
23.1 特定深度節點鏈表 145
23.2 後繼者 146
23.3 編譯順序 147
23.4 首個共同祖先 153
23.5 二叉搜索樹序列 158
23.6 檢查子樹 160
23.7 隨機節點 163
23.8 求和路徑 166
第 24 章 位操作 171
24.1 插入 171
24.2 二進制數轉字符串 172
24.3 下一個數 173
24.4 配對交換 177
第 25 章 數學與邏輯題 178
25.1 較重的藥丸 178
25.2 籃球問題 178
25.3 大災難 179
25.4 扔雞蛋問題 181
25.5 有毒的汽水 183
第 26 章 面向對象設計 190
26.1 撲克牌 190
26.2 客服中心 192
26.3 聊天軟件 194
26.4 環狀數組 198
26.5 掃雷 200
26.6 散列表 205
第 27 章 遞歸與動態規劃 207
27.1 三步問題 207
27.2 冪集 208
27.3 遞歸乘法 210
27.4 無重復字符串的排列組合 212
27.5 重復字符串的排列組合 215
27.6 括號 216
27.7 布爾運算 218
第 28 章 系統設計與可擴展性 221
28.1 網絡爬蟲 221
28.2 重復網址 222
28.3 緩存 222
28.4 銷售排名 225
28.5 個人理財管理 228
第 29 章 排序與查找 231
29.1 變位詞組 231
29.2 搜索輪轉數組 232
29.3 排序集合的查找 233
29.4 失蹤的整數 234
29.5 排序矩陣查找 238
29.6 峰與谷 241
第 30 章 數據庫 244
30.1 多套公寓 244
30.2 連接 244
30.3 反規範化 245
30.4 設計分級數據庫 246
第 31 章 C 和 C++ 248
31.1 最後 K 行 248
31.2 反轉字符串 249
31.3 散列表與 STL map 249
31.4 淺復制與深復制 250
31.5 volatile 關鍵字 251
31.6 分配內存 252
31.7 二維數組分配 253
第 32 章 Java 255
32.1 私有構造函數 255
32.2 final 們 255
32.3 泛型與模板 256
32.4 TreeMap、HashMap、LinkedHashMap 258
32.5 反射 259
32.6 lambda 表達式 259
第 33 章 線程與鎖 261
33.1 進程與線程 261
33.2 上下文切換 261
33.3 無死鎖的類 262
33.4 順序調用 266
33.5 FizzBuzz 268
第 34 章 測試 271
34.1 隨機崩潰 271
34.2 無工具測試 271
第 35 章 中等難題 273
35.1 交換數字 273
35.2 交點 274
35.3 最小差 276
35.4 整數的英文表示 277
35.5 運算 279
35.6 生存人數 282
35.7 部分排序 286
35.8 連續數列 288
35.9 模式匹配 290
35.10 交換求和 293
35.11 蘭頓螞蟻 296
35.12 1×5 個隨機數方法中生成 7 個隨機數 301
第 36 章 高難度題 304
36.1 不用加號的加法 304
36.2 消失的數字 305
36.3 字母與數字 307
36.4 2 出現的次數 310
36.5 主要元素 312
36.6 BiNode 315
36.7 最小 k 個數 318
36.8 多次搜索 323
36.9 消失的兩個數字 327
36.10 單詞轉換 331
36.11 最大子矩陣 336
36.12 稀疏相似度 341
第 37 章 進階話題 348
37.1 實用數學 348
37.1.1 整數 1 至 N 的和 348
37.1.2 2 的冪的和 349
37.1.3 對數的底 349
37.1.4 排列 349
37.1.5 組合 349
37.1.6 歸納證明 350
37.2 拓撲排序 350
37.3 Dijkstra 算法 351
37.4 散列表沖突解決方案 353
37.4.1 使用鏈表連接數據 354
37.4.2 使用二叉搜索樹連接數據 354
37.4.3 使用線性探測進行開放尋址 354
37.4.4 平方探測和雙重散列 354
37.5 Rabin-Karp 子串查找 354
37.6 AVL 樹 355
37.6.1 性質 355
37.6.2 插入操作 355
37.7 紅黑樹356
37.7.1 性質 357
37.7.2 為什麽這樣的樹是平衡的 357
37.7.3 插入操作 357
37.8 MapReduce 360
37.9 補充學習內容 361
