Python程序員面試寶典

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