程序員面試金典（第6版·修訂版）

第 一部分 求職準備 全面了解
第 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.*.* 省略細枝末節(jié) 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 國內企業(yè)的面試流程 9
2.5.2 國際企業(yè)面試的流程 11
2.6 面試成績 13
第 3 章 技術面試題 14
3.1 準備事項 14
*.* 基礎知識 14
*.*.1 核心數(shù)據(jù)結構、*法及概念 14
*.*.2 2 的冪表 15
3.3 解題步驟 15
3.3.1 認真聽 16
3.*.* 畫*例圖 17
3.3.3 給出一*蠻力法 17
3.3.4 優(yōu)化 17
3.3.5 梳理 18
3.3.6 實現(xiàn) 18
3.3.7 測試 19
3.4 優(yōu)化和解題技巧 19
3.4.1 尋找 BUD 19
3.4.2 親力親為 22
3.4.3 化繁為簡 23
3.4.4 由淺入深 23
3.4.5 數(shù)據(jù)結構頭腦風暴法 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 章 數(shù)組與字符串 52
5.1 散列表 52
5.2 ArrayList 與可變長度數(shù)組 53
5.3 StringBuilder 53
第 6 章 鏈表 55
6.1 創(chuàng)建鏈表 55
6.2 刪除單向鏈表中的節(jié)點 56
6.3 “快行指針”技巧 56
6.4 遞歸問題 56
第 7 章 棧與隊列 57
7.1 實現(xiàn)一*棧 57
7.2 實現(xiàn)一*隊列 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 深度優(yōu)先搜* 67
8.6.2 廣度優(yōu)先搜* 67
8.6.3 雙向搜* 68
第 9 章 位操作 69
9.1 手工位操作 69
9.2 位操作原理與技巧 69
9.3 二進制補碼與負數(shù) 70
9.4 *術右移與邏輯右移 70
9.5 常見位操作：獲取與設置數(shù)位 71
第 10 章 數(shù)學與邏輯題 73
10.1 素數(shù) 73
10.2 概率 75
10.3 總結規(guī)律和模式 76
第 11 章 面向對象設計 78
11.1 如何解答 78
11.2 設計模式 79
11.2.1 單例設計模式 79
11.2.2 工廠方法設計模式 79
第 12 章 遞歸與動態(tài)規(guī)劃 81
12.1 解題思路 81
12.2 遞歸與迭代 81
12.3 動態(tài)規(guī)劃及記憶法 82
第 13 章 系統(tǒng)設計與可擴展性 86
13.1 處理問題 86
1*.* 循環(huán)漸進的設計 87
13.3 逐步構建的方法：循序漸進 88
13.4 關鍵概念 88
13.5 系統(tǒng)設計要考慮的因素 90
13.6 實例演示 91
第 14 章 排序與查找 93
14.1 常見的排序*法 93
14.2 查找*法 95
第 15 章 數(shù)據(jù)庫 97
15.1 SQL 語法及各類變體 97
15.2 規(guī)范化數(shù)據(jù)庫和反規(guī)范化數(shù)據(jù)庫 97
15.3 SQL 語句 97
15.4 小型數(shù)據(jù)庫設計 99
15.5 大型數(shù)據(jù)庫設計 100
第 16 章 C 和 C 101
16.1 類和繼承 101
16.2 構造函數(shù)和析構函數(shù) 101
16.3 虛函數(shù)102
16.4 虛析構函數(shù) 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 測試現(xiàn)實生活中的事物 116
19.3 測試一套軟件 117
19.4 測試一*函數(shù) 119
19.5 調試與故障排除 119
第三部分 經典題型 輕松拿捏
第 20 章 數(shù)組與字符串 121
20.1 判定字符是否 121
20.2 URL 化 122
20.3 回文串排列 123
20.4 字符串壓縮 125
第 21 章 鏈表 128
21.1 返回倒數(shù)第 k *節(jié)點 128
21.2 鏈表求和 130
21.3 鏈表相交 132
21.4 環(huán)路檢測 135
第 22 章 棧與隊列 138
22.1 三合一 138
22.2 化棧為隊 142
22.3 棧排序 143
第 23 章 樹與圖 145
23.1 特定深度節(jié)點鏈表 145
2*.* 后繼者 146
23.3 編譯順序 147
23.4 **共同祖先 153
23.5 二叉搜*樹序列 158
23.6 檢查子樹 160
23.7 隨機節(jié)點 163
23.8 求和路徑 166
第 24 章 位操作 171
24.1 插入 171
24.2 二進制數(shù)轉字符串 172
24.3 下一*數(shù) 173
24.4 配對交換 177
第 25 章 數(shù)學與邏輯題 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 環(huán)狀數(shù)組 198
26.5 掃雷 200
26.6 散列表 205
第 27 章 遞歸與動態(tài)規(guī)劃 207
27.1 三步問題 207
27.2 冪集 208
27.3 遞歸乘法 210
27.4 無重復字符串的排列組合 212
27.5 重復字符串的排列組合 215
27.6 括號 216
27.7 布爾運* 218
第 28 章 系統(tǒng)設計與可擴展性 221
28.1 網(wǎng)絡爬蟲 221
28.2 重復網(wǎng)址 222
28.3 緩存 222
28.4 銷售排名 225
28.5 *人理財管理 228
第 29 章 排序與查找 231
29.1 變位詞組 231
29.2 搜*輪轉數(shù)組 232
29.3 排序集合的查找 233
29.4 失蹤的整數(shù) 234
29.5 排序矩陣查找 238
29.6 峰與谷 241
第 30 章 數(shù)據(jù)庫 244
30.1 多套公寓 244
30.2 連接 244
30.3 反規(guī)范化 245
30.4 設計分級數(shù)據(jù)庫 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 二維數(shù)組分配 253
第 32 章 Java 255
32.1 私有構造函數(shù) 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
3*.* 上下文切換 261
33.3 無死鎖的類 262
33.4 順序調用 266
33.5 FizzBuzz 268
第 34 章 測試 271
34.1 隨機崩潰 271
34.2 無工具測試 271
第 35 章 中等難題 273
35.1 交換數(shù)字 273
35.2 交點 274
35.3 小差 276
35.4 整數(shù)的英文表示 277
35.5 運* 279
35.6 生存人數(shù) 282
35.7 部分排序 286
35.8 連續(xù)數(shù)列 288
35.9 模式匹配 290
35.10 交換求和 293
35.11 蘭頓螞蟻 296
35.12 1×5 *隨機數(shù)方法中生成 7 *隨機數(shù) 301
第 36 章 高難度題 304
36.1 不用加號的加法 304
36.2 消失的數(shù)字 305
36.3 字母與數(shù)字 307
36.4 2 出現(xiàn)的次數(shù) 310
36.5 主要元素 312
36.6 BiNode 315
36.7 小 k *數(shù) 318
36.8 多次搜* 323
36.9 消失的兩*數(shù)字 327
36.10 單詞轉換 331
36.11 子矩陣 336
36.12 稀疏相似度 341
第 37 章 進階話題 348
37.1 實用數(shù)學 348
37.1.1 整數(shù) 1 至 N 的和 348
37.1.2 2 的冪的和 349
37.1.3 對數(shù)的底 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 使用鏈表連接數(shù)據(jù) 354
37.4.2 使用二叉搜*樹連接數(shù)據(jù) 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