Python 程序員面試寶典劍指 offer

陳屹

海南康康餅網絡科技有限公司CEO，15年開發麵試經驗，
曾在微軟、聯想、realplayer等公司承擔客戶端和服務器開發工作。
在算法設計、高並發、高性能服務器、複雜系統設計、人工智能等多個領域擁有深厚積累，
其設計的編譯原理、操作系統、網絡協議系統等多門原廠教學視頻在網易云課堂收到大量好評。

目錄
第1章技術面試的方法論 1
1.1 一道亞馬遜面試題的情景分析 1
1.1.1 暴力枚舉法 2
1.1.2 分而治之法 4
1.1.3 最優解法 6
1.1.4 解題流程總結 7
1.2 面試的流程，心態建設，相關準備 8
1.2.1 面試前流程 8
1.2.2 簡歷的製作10
1.2.3 有效的面試策略11
1.2.4 編碼實現12
1.2.5 面試過程中的交流要點13
1.3 知己知彼，百戰不殆——從面試官角度看面試14
1.3.1 如何進行一場良好的面試15
1.3.2 面試官如何主導面試流程17
1.3.3 面試官如何評估候選人17

第2章算法面試的技術路線圖19
2.1 算法面試中的數據結構19
2.1.1 基礎數據類型20
2.1.2 數組與字符串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 動態規劃29
2.2.5 貪婪算法29
2.2.6 逐步改進29
2.2.7 排除法30
2.3 抽象分析模式30
2.3.1 樣例覆蓋31
2.3.2 小量數據推導31
2.3.3 簡單方案的逐步改進32
2.3.4 問題還原33
2.3.5 圖論模擬34

第3章基礎數據類型的算法分析35
3.1 基礎數據類型中二進制位的操作算法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 代碼實現41
3.2.4 算法分析43
3.3 使用二進制求解最大公約數43
3.3.1 題目描述43
3.3.2 算法描述45
3.3.3 代碼實現47
3.3.4 算法分析49
3.4 素數判定50
3.4.1 題目描述50
3.4.2 算法描述50
3.4.3 代碼實現52
3.4.4 算法分析53
3.5 判斷矩形交集54
3.5.1 題目描述54
3.5.2 算法描述54
3.5.3 代碼實現56
3.6 數字與字符串相互轉化，簡單題目的隱藏陷阱58
3.6.1 題目描述58
3.6.2 算法描述58
3.6.3 代碼實現59
3.6.4 算法分析60
3.7 Elias Gamma編碼算法62
3.7.1 題目描述62
3.7.2 算法描述63
3.7.3 代碼實現63
3.7.4 算法分析66
3.8 整型的二進制乘法67
3.8.1 題目描述67
3.8.2 算法描述67
3.8.3 代碼實現69
3.8.4 算法分析73

第4章數組和字符串74
4.1 數組的定位排序74
4.1.1 題目描述74
4.1.2 算法描述75
4.1.3 代碼實現76
4.1.4 算法分析78
4.2 在整型數組中構建元素之和能整除數組長度的子集78
4.2.1 題目描述78
4.2.2 算法描述78
4.2.3 代碼實現79
4.2.4 算法分析82
4.3 計算等價類82
4.3.1 題目描述82
4.3.2 算法描述83
4.3.3 代碼實現85
4.3.4 代碼分析86
4.4 大型整數相乘87
4.4.1 題目描述87
4.4.2 算法描述87
4.4.3 代碼實現88
4.4.4 代碼分析91
4.5 數組的序列變換92
4.5.1 題目描述92
4.5.2 算法描述92
4.5.3 代碼實現94
4.5.4 代碼分析96
4.6 字符串的旋轉96
4.6.1 題目描述96
4.6.2 算法描述96
4.6.3 代碼實現97
4.6.4 代碼分析99
4.7 二維數組的啟發式搜索算法99
4.7.1 題目描述99
4.7.2 算法描述99
4.7.3 代碼實現100
4.7.4 代碼分析101
4.8 二維數組的旋轉遍歷102
4.8.1 題目描述102
4.8.2 算法描述102
4.8.3 代碼實現104
4.8.4 代碼分析105
4.9 矩陣的90°旋轉105
4.9.1 題目描述106
4.9.2 算法描述106
4.9.3 代碼實現107
4.9.4 代碼分析109
4.10 遊程編碼109
4.10.1 題目描述110
4.10.2 算法描述110
4.10.3 代碼實現110
4.10.4 代碼分析112
4.11 字符串中單詞的逆轉113
4.11.1 題目描述113
4.11.2 算法描述113
4.11.3 代碼實現114
4.11.4 代碼分析115
4.12 Rabin-Karp字符串匹配算法115
4.12.1 題目描述115
4.12.2 算法描述115
4.12.3 代碼實現118
4.12.4 代碼分析120
4.13 用有限狀態自動機匹配字符串120
4.13.1 題目描述120
4.13.2 算法描述121
4.13.3 代碼實現124
4.13.4 代碼分析127
4.14 KMP算法——字符串匹配算法的創意巔峰127
4.14.1 題目描述127
4.14.2 算法描述127
4.14.3 代碼實現129
4.14.4 代碼分析131
4.15 正則表達式引擎的設計和實施132
4.15.1 題目描述132
4.15.2 算法描述133
4.15.3 代碼實現138
4.15.4 代碼分析178

第5章隊列和鍊錶179
5.1 遞歸式實現鍊錶快速倒轉179
5.1.1 題目描述179
5.1.2 算法描述180
5.1.3 代碼實現181
5.1.4 代碼分析184
5.2 鍊錶成環檢測184
5.2.1 題目描述185
5.2.2 算法描述185
5.2.3 代碼實現186
5.2.4 代碼分析189
5.3 在O(1)時間內刪除單鍊錶非末尾節點190
5.3.1 題目描述190
5.3.2 算法描述190
5.3.3 代碼實現191
5.3.4 代碼分析192
5.4 獲取重合列表的第一個相交節點192
5.4.1 題目描述193
5.4.2 算法描述193
5.4.3 代碼實現194
5.4.4 代碼分析196
5.5 單向鍊錶的奇偶排序196
5.5.1 題目描述196
5.5.2 算法描述196
5.5.3 代碼實現198
5.5.4 代碼分析199
5.6 雙指針單向鍊錶的自我複制199
5.6.1 題目描述200
5.6.2 算法描述200
5.6.3 代碼實現202
5.6.4 代碼分析206
5.7 利用鍊錶層級打印二叉樹206
5.7.1 題目描述206
5.7.2 算法描述206
5.7.3 代碼實現207
5.7.4 代碼分析209

第6章堆棧和隊列210
6.1 利用堆棧計算逆向波蘭表達式210
6.1.1 題目描述210
6.1.2 算法描述210
6.1.3 代碼實現211
6.1.4 代碼分析213
6.2 計算堆棧當前元素最大值213
6.2.1 題目描述213
6.2.2 算法描述213
6.2.3 代碼實現214
6.2.4 代碼分析216
6.3 使用堆棧判斷括號匹配216
6.3.1 題目描述216
6.3.2 算法描述216
6.3.3 代碼實現217
6.3.4 代碼分析218
6.4 使用堆棧解決漢諾塔問題218
6.4.1 題目描述218
6.4.2 算法描述219
6.4.3 代碼實現219
6.4.4 代碼分析222
6.5 堆棧元素的在線排序222
6.5.1 題目描述223
6.5.2 算法描述223
6.5.3 代碼實現224
6.5.4 代碼分析225
6.6 計算滑動窗口內的最大網絡流量225
6.6.1 題目描述226
6.6.2 算法描述226
6.6.3 代碼實現231
6.6.4 代碼分析234
6.7 使用堆棧模擬隊列234
6.7.1 題目描述235
6.7.2 算法描述235
6.7.3 代碼實現235
6.7.4 代碼分析236

第7章二叉樹238
7.1 二叉樹的平衡性檢測238
7.1.1 題目描述239
7.1.2 算法描述239
7.1.3 代碼實現239
7.1.4 代碼分析242
7.2 鏡像二叉樹的檢測242
7.2.1 題目描述243
7.2.2 算法描述243
7.2.3 代碼實現244
7.2.4 代碼分析246
7.3 二叉樹的Morris遍曆法247
7.3.1 題目描述247
7.3.2 算法描述247
7.3.3 代碼實現250
7.3.4 代碼分析251
7.4 使用前序遍歷和中序遍歷重構二叉樹252
7.4.1 題目描述252
7.4.2 算法描述253
7.4.3 代碼實現254
7.4.4 代碼分析256
7.5 逆時針打印二叉樹外圍邊緣256
7.5.1 題目描述256
7.5.2 算法描述257
7.5.3 代碼實現257
7.5.4 代碼分析259
7.6 尋找兩個二叉樹節點的最近共同祖先259
7.6.1 題目描述260
7.6.2 算法描述260
7.6.3 代碼實現260
7.6.4 代碼分析264
7.7 設計搜索輸入框的輸入提示功能264
7.7.1 題目描述264
7.7.2 算法描述264
7.7.3 代碼實現265
7.7.4 代碼分析269

第8章堆270
8.1 使用堆排序實現系統Timer機制270
8.1.1 題目描述270
8.1.2 算法描述270
8.1.3 代碼實現273
8.1.4 代碼分析279
8.2 波浪形數組的快速排序法279
8.2.1 題目描述279
8.2.2 算法描述280
8.2.3 代碼實現281
8.2.4 代碼分析287
8.3 快速獲取數組中點的相鄰區域點287
8.3.1 題目描述287
8.3.2 算法描述287
8.3.3 代碼實現289
8.3.4 代碼分析292

第9章二分查找法293
9.1 隱藏在《編程珠璣》中20年的bug 293
9.1.1 題目描述294
9.1.2 算法描述294
9.1.3 代碼實現295
9.1.4 代碼分析297
9.2 在lg(k)時間內查找兩個排序數組合併後第k小元素297
9.2.1 題目描述297
9.2.2 算法描述297
9.2.3 代碼實現299
9.2.4 代碼分析301
9.3 二分查找法尋求數組截斷點302
9.3.1 題目描述302
9.3.2 算法描述302
9.3.3 代碼實現304
9.3.4 代碼分析306
9.4 在雙升序數組中快速查找給定值306
9.4.1 題目描述307
9.4.2 算法描述307
9.4.3 代碼實現307
9.4.4 代碼分析309

第10章圖論310
10.1 地圖著色問題310
10.1.1 問題描述310
10.1.2 算法描述310
10.1.3 代碼實現311
10.1.4 代碼分析315
10.2 迪傑斯特拉最短路徑算法316
10.2.1 題目描述316
10.2.2 算法描述316
10.2.3 代碼實現319
10.2.4 代碼分析326
10.3 使用深度優先搜索解決容器倒水問題327