Python程序員面試寶典

第1章 技術(shù)面試的方法論 1
1.1 一道亞馬遜面試題的情景分析 1
1.1.1 暴力枚舉法 2
1.1.2 分而治之法 4
1.1.3 最優(yōu)解法 6
1.1.4 解題流程總結(jié) 7
1.2 面試的流程，心態(tài)建設(shè)，相關(guān)準(zhǔn)備 8
1.2.1 面試前流程 8
1.2.2 簡(jiǎn)歷的制作 10
1.2.3 有效的面試策略 11
1.2.4 編碼實(shí)現(xiàn) 12
1.2.5 面試過程中的交流要點(diǎn) 13
1.3 知己知彼，百戰(zhàn)不殆——從面試官角度看面試 14
1.3.1 如何進(jìn)行一場(chǎng)良好的面試 15
1.3.2 面試官如何主導(dǎo)面試流程 17
1.3.3 面試官如何評(píng)估候選人 17
第2章 算法面試的技術(shù)路線圖 19
2.1 算法面試中的數(shù)據(jù)結(jié)構(gòu) 19
2.1.1 基礎(chǔ)數(shù)據(jù)類型 20
2.1.2 數(shù)組與字符串 21
2.1.3 鏈表 21
2.1.4 堆棧 22
2.1.5 二叉樹 22
2.1.6 堆 23
2.1.7 哈希表 23
2.2 算法的設(shè)計(jì)模式 24
2.2.1 排序 24
2.2.2 遞歸 26
2.2.3 分而治之 27
2.2.4 動(dòng)態(tài)規(guī)劃 29
2.2.5 貪婪算法 29
2.2.6 逐步改進(jìn) 29
2.2.7 排除法 30
2.3 抽象分析模式 30
2.3.1 樣例覆蓋 31
2.3.2 小量數(shù)據(jù)推導(dǎo) 31
2.3.3 簡(jiǎn)單方案的逐步改進(jìn) 32
2.3.4 問題還原 33
2.3.5 圖論模擬 34
第3章 基礎(chǔ)數(shù)據(jù)類型的算法分析 35
3.1 基礎(chǔ)數(shù)據(jù)類型中二進(jìn)制位的操作算法 35
3.1.1 整型變量值互換 35
3.1.2 常用的二進(jìn)制位操作 36
3.1.3 解析一道二進(jìn)制操作相關(guān)算法面試題 37
3.1.4 總結(jié) 40
3.2 用二進(jìn)制操作求解集合所有子集 40
3.2.1 題目描述 40
3.2.2 算法描述 40
3.2.3 代碼實(shí)現(xiàn) 41
3.2.4 算法分析 43
3.3 使用二進(jìn)制求解最大公約數(shù) 43
3.3.1 題目描述 43
3.3.2 算法描述 45
3.3.3 代碼實(shí)現(xiàn) 47
3.3.4 算法分析 49
3.4 素?cái)?shù)判定 50
3.4.1 題目描述 50
3.4.2 算法描述 50
3.4.3 代碼實(shí)現(xiàn) 52
3.4.4 算法分析 53
3.5 判斷矩形交集 54
3.5.1 題目描述 54
3.5.2 算法描述 54
3.5.3 代碼實(shí)現(xiàn) 56
3.6 數(shù)字與字符串相互轉(zhuǎn)化，簡(jiǎn)單題目的隱藏陷阱 58
3.6.1 題目描述 58
3.6.2 算法描述 58
3.6.3 代碼實(shí)現(xiàn) 59
3.6.4 算法分析 60
3.7 Elias Gamma編碼算法 62
3.7.1 題目描述 62
3.7.2 算法描述 63
3.7.3 代碼實(shí)現(xiàn) 63
3.7.4 算法分析 66
3.8 整型的二進(jìn)制乘法 67
3.8.1 題目描述 67
3.8.2 算法描述 67
3.8.3 代碼實(shí)現(xiàn) 69
3.8.4 算法分析 73
第4章 數(shù)組和字符串 74
4.1 數(shù)組的定位排序 74
4.1.1 題目描述 74
4.1.2 算法描述 75
4.1.3 代碼實(shí)現(xiàn) 76
4.1.4 算法分析 78
4.2 在整型數(shù)組中構(gòu)建元素之和能整除數(shù)組長(zhǎng)度的子集 78
4.2.1 題目描述 78
4.2.2 算法描述 78
4.2.3 代碼實(shí)現(xiàn) 79
4.2.4 算法分析 82
4.3 計(jì)算等價(jià)類 82
4.3.1 題目描述 82
4.3.2 算法描述 83
4.3.3 代碼實(shí)現(xiàn) 85
4.3.4 代碼分析 86
4.4 大型整數(shù)相乘 87
4.4.1 題目描述 87
4.4.2 算法描述 87
4.4.3 代碼實(shí)現(xiàn) 88
4.4.4 代碼分析 91
4.5 數(shù)組的序列變換 92
4.5.1 題目描述 92
4.5.2 算法描述 92
4.5.3 代碼實(shí)現(xiàn) 94
4.5.4 代碼分析 96
4.6 字符串的旋轉(zhuǎn) 96
4.6.1 題目描述 96
4.6.2 算法描述 96
4.6.3 代碼實(shí)現(xiàn) 97
4.6.4 代碼分析 99
4.7 二維數(shù)組的啟發(fā)式搜索算法 99
4.7.1 題目描述 99
4.7.2 算法描述 99
4.7.3 代碼實(shí)現(xiàn) 100
4.7.4 代碼分析 101
4.8 二維數(shù)組的旋轉(zhuǎn)遍歷 102
4.8.1 題目描述 102
4.8.2 算法描述 102
4.8.3 代碼實(shí)現(xiàn) 104
4.8.4 代碼分析 105
4.9 矩陣的90°旋轉(zhuǎn) 105
4.9.1 題目描述 106
4.9.2 算法描述 106
4.9.3 代碼實(shí)現(xiàn) 107
4.9.4 代碼分析 109
4.10 游程編碼 109
4.10.1 題目描述 110
4.10.2 算法描述 110
4.10.3 代碼實(shí)現(xiàn) 110
4.10.4 代碼分析 112
4.11 字符串中單詞的逆轉(zhuǎn) 113
4.11.1 題目描述 113
4.11.2 算法描述 113
4.11.3 代碼實(shí)現(xiàn) 114
4.11.4 代碼分析 115
4.12 Rabin-Karp字符串匹配算法 115
4.12.1 題目描述 115
4.12.2 算法描述 115
4.12.3 代碼實(shí)現(xiàn) 118
4.12.4 代碼分析 120
4.13 用有限狀態(tài)自動(dòng)機(jī)匹配字符串 120
4.13.1 題目描述 120
4.13.2 算法描述 121
4.13.3 代碼實(shí)現(xiàn) 124
4.13.4 代碼分析 127
4.14 KMP算法——字符串匹配算法的創(chuàng)意巔峰 127
4.14.1 題目描述 127
4.14.2 算法描述 127
4.14.3 代碼實(shí)現(xiàn) 129
4.14.4 代碼分析 131
4.15 正則表達(dá)式引擎的設(shè)計(jì)和實(shí)施 132
4.15.1 題目描述 132
4.15.2 算法描述 133
4.15.3 代碼實(shí)現(xiàn) 138
4.15.4 代碼分析 178
第5章 隊(duì)列和鏈表 179
5.1 遞歸式實(shí)現(xiàn)鏈表快速倒轉(zhuǎn) 179
5.1.1 題目描述 179
5.1.2 算法描述 180
5.1.3 代碼實(shí)現(xiàn) 181
5.1.4 代碼分析 184
5.2 鏈表成環(huán)檢測(cè) 184
5.2.1 題目描述 185
5.2.2 算法描述 185
5.2.3 代碼實(shí)現(xiàn) 186
5.2.4 代碼分析 189
5.3 在O(1)時(shí)間內(nèi)刪除單鏈表非末尾節(jié)點(diǎn) 190
5.3.1 題目描述 190
5.3.2 算法描述 190
5.3.3 代碼實(shí)現(xiàn) 191
5.3.4 代碼分析 192
5.4 獲取重合列表的第一個(gè)相交節(jié)點(diǎn) 192
5.4.1 題目描述 193
5.4.2 算法描述 193
5.4.3 代碼實(shí)現(xiàn) 194
5.4.4 代碼分析 196
5.5 單向鏈表的奇偶排序 196
5.5.1 題目描述 196
5.5.2 算法描述 196
5.5.3 代碼實(shí)現(xiàn) 198
5.5.4 代碼分析 199
5.6 雙指針單向鏈表的自我復(fù)制 199
5.6.1 題目描述 200
5.6.2 算法描述 200
5.6.3 代碼實(shí)現(xiàn) 202
5.6.4 代碼分析 206
5.7 利用鏈表層級(jí)打印二叉樹 206
5.7.1 題目描述 206
5.7.2 算法描述 206
5.7.3 代碼實(shí)現(xiàn) 207
5.7.4 代碼分析 209
第6章 堆棧和隊(duì)列 210
6.1 利用堆棧計(jì)算逆向波蘭表達(dá)式 210
6.1.1 題目描述 210
6.1.2 算法描述 210
6.1.3 代碼實(shí)現(xiàn) 211
6.1.4 代碼分析 213
6.2 計(jì)算堆棧當(dāng)前元素最大值 213
6.2.1 題目描述 213
6.2.2 算法描述 213
6.2.3 代碼實(shí)現(xiàn) 214
6.2.4 代碼分析 216
6.3 使用堆棧判斷括號(hào)匹配 216
6.3.1 題目描述 216
6.3.2 算法描述 216
6.3.3 代碼實(shí)現(xiàn) 217
6.3.4 代碼分析 218
6.4 使用堆棧解決漢諾塔問題 218
6.4.1 題目描述 218
6.4.2 算法描述 219
6.4.3 代碼實(shí)現(xiàn) 219
6.4.4 代碼分析 222
6.5 堆棧元素的在線排序 222
6.5.1 題目描述 223
6.5.2 算法描述 223
6.5.3 代碼實(shí)現(xiàn) 224
6.5.4 代碼分析 225
6.6 計(jì)算滑動(dòng)窗口內(nèi)的最大網(wǎng)絡(luò)流量 225
6.6.1 題目描述 226
6.6.2 算法描述 226
6.6.3 代碼實(shí)現(xiàn) 231
6.6.4 代碼分析 234
6.7 使用堆棧模擬隊(duì)列 234
6.7.1 題目描述 235
6.7.2 算法描述 235
6.7.3 代碼實(shí)現(xiàn) 235
6.7.4 代碼分析 236
第7章 二叉樹 238
7.1 二叉樹的平衡性檢測(cè) 238
7.1.1 題目描述 239
7.1.2 算法描述 239
7.1.3 代碼實(shí)現(xiàn) 239
7.1.4 代碼分析 242
7.2 鏡像二叉樹的檢測(cè) 242
7.2.1 題目描述 243
7.2.2 算法描述 243
7.2.3 代碼實(shí)現(xiàn) 244
7.2.4 代碼分析 246
7.3 二叉樹的Morris遍歷法 247
7.3.1 題目描述 247
7.3.2 算法描述 247
7.3.3 代碼實(shí)現(xiàn) 250
7.3.4 代碼分析 251
7.4 使用前序遍歷和中序遍歷重構(gòu)二叉樹 252
7.4.1 題目描述 252
7.4.2 算法描述 253
7.4.3 代碼實(shí)現(xiàn) 254
7.4.4 代碼分析 256
7.5 逆時(shí)針打印二叉樹外圍邊緣 256
7.5.1 題目描述 256
7.5.2 算法描述 257
7.5.3 代碼實(shí)現(xiàn) 257
7.5.4 代碼分析 259
7.6 尋找兩個(gè)二叉樹節(jié)點(diǎn)的最近共同祖先 259
7.6.1 題目描述 260
7.6.2 算法描述 260
7.6.3 代碼實(shí)現(xiàn) 260
7.6.4 代碼分析 264
7.7 設(shè)計(jì)搜索輸入框的輸入提示功能 264
7.7.1 題目描述 264
7.7.2 算法描述 264
7.7.3 代碼實(shí)現(xiàn) 265
7.7.4 代碼分析 269
第8章 堆 270
8.1 使用堆排序?qū)崿F(xiàn)系統(tǒng)Timer機(jī)制 270
8.1.1 題目描述 270
8.1.2 算法描述 270
8.1.3 代碼實(shí)現(xiàn) 273
8.1.4 代碼分析 279
8.2 波浪形數(shù)組的快速排序法 279
8.2.1 題目描述 279
8.2.2 算法描述 280
8.2.3 代碼實(shí)現(xiàn) 281
8.2.4 代碼分析 287
8.3 快速獲取數(shù)組中點(diǎn)的相鄰區(qū)域點(diǎn) 287
8.3.1 題目描述 287
8.3.2 算法描述 287
8.3.3 代碼實(shí)現(xiàn) 289
8.3.4 代碼分析 292
第9章 二分查找法 293
9.1 隱藏在《編程珠璣》中20年的bug 293
9.1.1 題目描述 294
9.1.2 算法描述 294
9.1.3 代碼實(shí)現(xiàn) 295
9.1.4 代碼分析 297
9.2 在lg(k)時(shí)間內(nèi)查找兩個(gè)排序數(shù)組合并后第k小元素 297
9.2.1 題目描述 297
9.2.2 算法描述 297
9.2.3 代碼實(shí)現(xiàn) 299
9.2.4 代碼分析 301
9.3 二分查找法尋求數(shù)組截?cái)帱c(diǎn) 302
9.3.1 題目描述 302
9.3.2 算法描述 302
9.3.3 代碼實(shí)現(xiàn) 304
9.3.4 代碼分析 306
9.4 在雙升序數(shù)組中快速查找給定值 306
9.4.1 題目描述 307
9.4.2 算法描述 307
9.4.3 代碼實(shí)現(xiàn) 307
9.4.4 代碼分析 309
第10章 圖論 310
10.1 地圖著色問題 310
10.1.1 問題描述 310
10.1.2 算法描述 310
10.1.3 代碼實(shí)現(xiàn) 311
10.1.4 代碼分析 315
10.2 迪杰斯特拉最短路徑算法 316
10.2.1 題目描述 316
10.2.2 算法描述 316
10.2.3 代碼實(shí)現(xiàn) 319
10.2.4 代碼分析 326
10.3 使用深度優(yōu)先搜索解決容器倒水問題 327
10.3.1 問題描述 327
10.3.2 算法描述 327
10.3.3 代碼實(shí)現(xiàn) 329
10.3.4 代碼分析 333
第11章 貪婪算法 335
11.1 最小生成樹 335
11.1.1 題目描述 335
11.1.2 算法描述 336
11.1.3 代碼實(shí)現(xiàn) 339
11.1.4 代碼分析 344
11.2 霍夫曼編碼 344
11.2.1 題目描述 345
11.2.2 算法描述 345
11.2.3 代碼實(shí)現(xiàn) 347
11.2.4 代碼分析 349
11.3 離散點(diǎn)集的最大覆蓋率問題 350
11.3.1 題目描述 350
11.3.2 算法描述 351
11.3.3 代碼實(shí)現(xiàn) 352
11.3.4 代碼分析 355
第12章 動(dòng)態(tài)規(guī)劃 356
12.1 鋼管最優(yōu)切割方案 356
12.1.1 問題描述 357
12.1.2 算法描述 357
12.1.3 代碼實(shí)現(xiàn) 358
12.1.4 代碼分析 360
12.2 查找最大共同子串 361
12.2.1 問題描述 362
12.2.2 算法描述 362
12.2.3 代碼實(shí)現(xiàn) 364
12.2.4 代碼分析 366
12.3 將最大共同子串算法的空間復(fù)雜度從O(n2)改進(jìn)為O(n) 366
12.3.1 問題描述 367
12.3.2 算法描述 367
12.3.3 代碼實(shí)現(xiàn) 368
12.3.4 代碼分析 371