矽谷 Python 工程師面試指南：資料結構、演算法與系統設計

Contents目錄
前　言
第一部分　面試流程
第1章　矽谷公司面試流程　2
1.1　非技術電話面試　　2
1.2　技術電話面試　　3
1.2.1　閒聊環節　3
1.2.2　技術溝通環節　3
1.2.3　提問環節　4
1.3　現場面試　　4
1.3.1　準備好閒聊素材　5
1.3.2　保持積極溝通　6
第二部分　資料結構
第2章　列表　8
2.1　列表的基礎知識　　8
2.1.1　創建列表　8
2.1.2　在清單中新增元素　9
2.1.3　刪除清單中的元素　11
2.2　實例1：最長連續1的個數　　12
2.3　實例2：二進位相加　　13
2.4　實例3：查詢範圍和　　15
2.4.1　利用一維數組求解　16
2.4.2　利用二維數組求解　16
2.5　實例4：隨機索引　　18
2.6　實例5：下一個更大排列　　19
2.7　實例6：驗證有效數字　　21
2.8　實例7：遞歸小數　　23
第3章　堆棧　25
3.1　堆疊的基礎知識　　25
3.1.1　堆疊操作及時間複雜度　25
3.1.2　3種實作方式　26
3.1.3　堆疊的應用　29
3.2　實例1：透過最小移除操作得到有效的括號　　29
3.3　實例2：函數的專用時間　　30
第4章　隊列　33
4.1　隊列的3種實作方式　　33
4.2　實例1：設計循環佇列　　36
4.3　實例2：求和大於K的最短非空連續子數組的長度　　38
第5章　優先隊列　40
5.1　優先隊列的3種實作方式　　40
5.2　實例1：僱用K個工人的最低成本　　42
5.3　實例2：判斷數組是否可以拆分為連續的子序列　　43
第6章　字典　45
6.1　字典的基礎知識　　45
6.1.1　創建字典　45
6.1.2　在字典中加入元素　46
6.1.3　訪問字典中的元素　48
6.1.4　從字典中刪除元素　49
6.2　實例1：和等於K的連續子數組的總數　　50
6.3　實例2：標籤中的最大值　　51
6.4　實例3：以平均時間複雜度O(1)實現插入、刪除和取得隨機值　　52
6.5　實例4：最近最少使用快取　　54
第7章　集合　57
7.1　集合的基礎知識　　57
7.2　集合的基本運算　　58
7.2.1　添加元素　58
7.2.2　刪除元素　59
7.2.3　並集　59
7.2.4　交集　60
第8章　鍊錶　61
8.1　雙指針技術　　61
8.2　實例1：判斷鍊錶是否有循環　　62
8.3　實例2：兩個鍊錶的交集　　62
8.4　實例3：克隆隨機鍊錶　　64
8.5　實例4：反轉鍊錶　　65
第9章　二叉樹　66
9.1　層次順序遍歷　　66
9.1.1　前序遍歷　66
9.1.2　中序遍歷　67
9.1.3　後序遍歷　68
9.1.4　層序遍歷　69
9.2　遞歸法用於樹的遍歷　　69
9.2.1　自上而下的解決方案　70
9.2.2　自下而上的解　70
9.3　實例1：二元樹的最低共同祖先　　72
9.4　實例2：序列化與反序列化二元樹　　73
9.5　實例3：求二元樹的最大路徑和　　74
9.6　實例4：將二元樹轉換為雙鍊錶　　75
第10章　其他樹狀結構　77
10.1　前綴樹　　77
10.1.1　前綴樹節點的資料結構　78
10.1.2　在前綴樹中插入單字　78
10.1.3　在前綴樹中搜尋單字　80
10.2　線段樹　　82
10.3　二元索引樹　　86
10.3.1　二元索引樹的表示　87
10.3.2　getSum操作　87
10.3.3　update操作　88
10.3.4　二元索引樹的工作原理　89
10.4　實例1：範圍和的個數　　90
10.4.1　利用線段樹求解　90
10.4.2　利用二元索引樹求解　94
10.4.3　利用二分搜尋求解　96
10.5　實例2：計算後面較小數字的個數　　97
10.5.1　二元索引樹解法　97
10.5.2　二分搜尋解法　98
10.5.3　線段樹解法　99
第11章　圖　100
11.1　圖的表示　　100
11.1.1　鄰接矩陣　100
11.1.2　鄰接表　101
11.2　實例1：克隆圖　　103
11.3　實例2：圖驗證樹　　104
11.3.1　深度優先搜尋解法　104
11.3.2　廣度優先搜尋解法　106
11.3.3　並查集解法　107
第三部分　演算法
第12章　二分搜尋　110
12.1　實例1：求平方根　　110
12.2　實例2：在旋轉排序數組中搜尋　　111
12.3　案例3：會議室預約問題　　112
12.3.1　問題1：如何最佳化　112
12.3.2　問題2：如何預約多個房間　113
第13章　雙指針法　114
13.1　實例1：稀疏向量的點積　　114
13.2　實例2：最小視窗子字串　　115
13.3　實例3：間隔清單相交　　116
13.4　實例4：最長連續1的個數　　119
13.5　實例5：找出字串中的所有字母　　121
第14章　動態規劃　123
14.1　動態規劃的基礎知識　　123
14.2　實例1：買賣股票的最佳時間　　124
14.3　實例2：硬幣找零　　124
14.4　實例3：計算解碼方式總數　　125
第15章　深度優先搜尋　127
15.1　深度優先搜尋的應用　　127
15.2　實例1：太平洋與大西洋的水流問題　　128
15.3　實例2：預測獲勝者　　129
15.4　實例3：表達式加運算子　　130
第16章　回溯　132
16.1　實例1：數獨求解　　132
16.2　實例2：掃地機器人　　135
第17章　廣度優先搜尋　137
17.1　廣度優先搜尋的應用程式　　138
17.2　實例1：牆與門　　139
17.3　實例2：課程表　　141
17.4　實例3：公車路線　　142
17.5　實例4：判斷二分圖　　143
17.6　實例5：單字階梯　　145
第18章　並查集　147
18.1　並查集的基礎知識　　147
18.2　實例：朋友圈　　150
18.2.1　廣度優先搜尋解法　150
18.2.2　深度優先搜尋解法　151
18.2.3　並查集解法　152
第19章　資料結構與演算法面試真題實戰　153
19.1　實例1：檔案系統　　153
19.1.1　關於資料結構的探討　154
19.1.2　面試題考查點　156
19.1.3　完整代碼　156
19.2　實例2：最長有效詞　　157
19.2.1　找到更快的解　158
19.2.2　基於儲存/快取的解決方案　159
19.2.3　面試題考查點　161
19.3　實例3：圓圈組　　161
19.3.1　圓圈組的個數　163
19.3.2　最大的k個圓圈組　163
第四部分　系統設計
第20章　系統設計理論　166
20.1　設計步驟　　166
20.1.1　描述使用情境、限制與假設　166
20.1.2　建造高層設計　166
20.1.3　設計核心組件　167
20.1.4　擴展設計　169
20.2　域名系統　　171
20.3　負載平衡器　　172
20.4　分散式快取系統　　173
20.5　哈希一致性　　176
第21章　系統設計實戰　178
21.1　設計分散式快取系統　　178
21.1.1　快取無效　178
21.1.2　緩存逐出策略　179
21.1.3　設計分散式鍵值快取系統　180
21.2　設計網路爬蟲系統　　181
21.2.1　架構設計　181
21.2.2　爬蟲類服務　181
21.2.3　處理重複連結　183
21.2.4　更新爬網結果　184
21.2.5　可擴充性設計　184
21.3　TinyURL的加密與解密　　185
21.3.1　系統的要求與目標　185
21.3.2　容量估算與約束　185
21.3.3　系統API　186
21.3.4　核心演算法設計　187
21.3.5　資料庫設計　187
21.3.6　資料分區與複製　188
21.3.7　緩存　188
21.3.8　負載平衡器　189
21.4　設計自動補全功能　　189
21.4.1　基本系統設計與演算法　190
21.4.2　主資料結構　191
21.4.3　最佳化設計　192
21.5　設計新聞動態功能　　195
21.6　設計X（Twitter）應用　　198
21.7　設計Uber/Lyft應用　　203
第22章　多執行緒程式設計　206
22.1　多執行緒面試問題　　206
22.2　實例1：形成水分子　　207
22.3　實例2：列印零、偶數、奇數　　208
第23章　設計機器學習系統　210
23.1　機器學習的基礎知識　　210
23.1.1　什麼是機器學習　210
23.1.2　為什麼要使用機器學習　211
23.1.3　監督學習與無監督學習　212
23.1.4　分類模型與迴歸模型　213
23.1.5　轉換問題　214
23.1.6　關鍵資料　214
23.1.7　機器學習工作流程　215
23.1.8　欠擬合與過擬合　216
23.1.9　偏差與變異數　217
23.2　機器學習的進階知識　　220
23.2.1　處理不平衡的二進位分類　220
23.2.2　高斯混合模型與K平均值的比較　221
23.2.3　梯度提升　221
23.2.4　決策樹的限制　223
23.2.5　加權更新　223
23.2.6　隨機梯度提升　223
23.2.7　懲罰性學習　224
23.3　機器學習面試　　224
23.3.1　機器學習面試考查點　224
23.3.2　機器學習面試的想法　226
23.4　實例1：搜尋排名系統　　227
23.4.1　題目解讀　227
23.4.2　指標分析　228
23.4.3　架構　229
23.4.4　結果選擇　231
23.4.5　訓練資料產生　237
23.4.6　排名　238
23.4.7　篩選結果　240
23.5　實例2：Netflix電影推薦系統　　242
23.5.1　題目解讀　242
23.5.2　指標分析　244
23.5.3　架構　246
23.5.4　特徵工程　247
23.5.5　候選電影的產生　250
23.5.6　訓練資料產生　252
23.5.7　排名　253