Contents?目　　錄
前　言
第一部分　面試流程
第1章　硅谷公司面試流程　2
1.1　非技術(shù)電話面試　　2
1.2　技術(shù)電話面試　　3
1.2.1　閑談環(huán)節(jié)　3
1.2.2　技術(shù)溝通環(huán)節(jié)　3
1.2.3　提問環(huán)節(jié)　4
1.3　現(xiàn)場面試　　4
1.3.1　準(zhǔn)備好閑談素材　5
1.3.2　保持積極溝通　6
第二部分　數(shù)據(jù)結(jié)構(gòu)
第2章　列表　8
2.1　列表的基礎(chǔ)知識　　8
2.1.1　創(chuàng)建列表　8
2.1.2　向列表中添加元素　9
2.1.3　刪除列表中的元素　11
2.2　實(shí)例1：最長連續(xù)1的個(gè)數(shù)　　12
2.3　實(shí)例2：二進(jìn)制相加　　13
2.4　實(shí)例3：查詢范圍和　　15
2.4.1　利用一維數(shù)組求解　16
2.4.2　利用二維數(shù)組求解　16
2.5　實(shí)例4：隨機(jī)索引　　18
2.6　實(shí)例5：下一個(gè)更大排列　　19
2.7　實(shí)例6：驗(yàn)證有效數(shù)字　　21
2.8　實(shí)例7：遞歸小數(shù)　　23
第3章　堆�！�25
3.1　堆棧的基礎(chǔ)知識　　25
3.1.1　堆棧操作及時(shí)間復(fù)雜度　25
3.1.2　3種實(shí)現(xiàn)方式　26
3.1.3　堆棧的應(yīng)用　29
3.2　實(shí)例1：通過最小移除操作
得到有效的括號　　29
3.3　實(shí)例2：函數(shù)的專用時(shí)間　　30
第4章　隊(duì)列　33
4.1　隊(duì)列的3種實(shí)現(xiàn)方式　　33
4.2　實(shí)例1：設(shè)計(jì)循環(huán)隊(duì)列　　36
4.3　實(shí)例2：求和大于K的最短
非空連續(xù)子數(shù)組的長度　　38
第5章　優(yōu)先隊(duì)列　40
5.1　優(yōu)先隊(duì)列的3種實(shí)現(xiàn)方式　　40
5.2　實(shí)例1：雇用K個(gè)工人的最低
成本　　42
5.3　實(shí)例2：判斷數(shù)組是否可以
拆分為連續(xù)的子序列　　43
第6章　字典　45
6.1　字典的基礎(chǔ)知識　　45
6.1.1　創(chuàng)建字典　45
6.1.2　向字典中添加元素　46
6.1.3　訪問字典中的元素　48
6.1.4　從字典中刪除元素　49
6.2　實(shí)例1：和等于K的連續(xù)子
數(shù)組的總數(shù)　　50
6.3　實(shí)例2：標(biāo)簽中的最大值　　51
6.4　實(shí)例3：以平均時(shí)間復(fù)雜度
O(1)實(shí)現(xiàn)插入、刪除和獲取
隨機(jī)值　　52
6.5　實(shí)例4：最近最少使用緩存　　54
第7章　集合　57
7.1　集合的基礎(chǔ)知識　　57
7.2　集合的基本操作　　58
7.2.1　添加元素　58
7.2.2　刪除元素　59
7.2.3　并集　59
7.2.4　交集　60
第8章　鏈表　61
8.1　雙指針技術(shù)　　61
8.2　實(shí)例1：判斷鏈表是否有循環(huán)　　62
8.3　實(shí)例2：兩個(gè)鏈表的交集　　62
8.4　實(shí)例3：克隆隨機(jī)鏈表　　64
8.5　實(shí)例4：反轉(zhuǎn)鏈表　　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　實(shí)例1：二叉樹的最低共同
祖先　　72
9.4　實(shí)例2：序列化和反序列化
二叉樹　　73
9.5　實(shí)例3：求二叉樹的最大
路徑和　　74
9.6　實(shí)例4：將二叉樹轉(zhuǎn)換為
雙鏈表　　75
第10章　其他樹結(jié)構(gòu)　77
10.1　前綴樹　　77
10.1.1　前綴樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)　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　實(shí)例1：范圍和的個(gè)數(shù)　　90
10.4.1　利用線段樹求解　90
10.4.2　利用二叉索引樹求解　94
10.4.3　利用二分搜索求解　96
10.5　實(shí)例2：計(jì)算后面較小數(shù)字的
個(gè)數(shù)　　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　實(shí)例1：克隆圖　　103
11.3　實(shí)例2：圖驗(yàn)證樹　　104
11.3.1　深度優(yōu)先搜索解法　104
11.3.2　廣度優(yōu)先搜索解法　106
11.3.3　并查集解法　107
第三部分　算法
第12章　二分搜索　110
12.1　實(shí)例1：求平方根　　110
12.2　實(shí)例2：在旋轉(zhuǎn)排序數(shù)組中
搜索　　111
12.3　案例3：會(huì)議室預(yù)訂問題　　112
12.3.1　問題1：如何優(yōu)化　112
12.3.2　問題2：如何預(yù)訂多個(gè)
房間　113
第13章　雙指針法　114
13.1　實(shí)例1：稀疏向量的點(diǎn)積　　114
13.2　實(shí)例2：最小窗口子字符串　　115
13.3　實(shí)例3：間隔列表相交　　116
13.4　實(shí)例4：最長連續(xù)1的個(gè)數(shù)　　119
13.5　實(shí)例5：查找字符串中的所有
字母　　121
第14章　動(dòng)態(tài)規(guī)劃　123
14.1　動(dòng)態(tài)規(guī)劃的基礎(chǔ)知識　　123
14.2　實(shí)例1：買賣股票的最佳
時(shí)間　　124
14.3　實(shí)例2：硬幣找零　　124
14.4　實(shí)例3：計(jì)算解碼方式
總數(shù)　　125
第15章　深度優(yōu)先搜索　127
15.1　深度優(yōu)先搜索的應(yīng)用　　127
15.2　實(shí)例1：太平洋和大西洋的
水流問題　　128
15.3　實(shí)例2：預(yù)測獲勝者　　129
15.4　實(shí)例3：表達(dá)式加運(yùn)算符　　130
第16章　回溯　132
16.1　實(shí)例1：數(shù)獨(dú)求解　　132
16.2　實(shí)例2：掃地機(jī)器人　　135
第17章　廣度優(yōu)先搜索　137
17.1　廣度優(yōu)先搜索的應(yīng)用　　138
17.2　實(shí)例1：墻和門　　139
17.3　實(shí)例2：課程表　　141
17.4　實(shí)例3：公交路線　　142
17.5　實(shí)例4：判斷二分圖　　143
17.6　實(shí)例5：單詞階梯　　145
第18章　并查集　147
18.1　并查集的基礎(chǔ)知識　　147
18.2　實(shí)例：朋友圈　　150
18.2.1　廣度優(yōu)先搜索解法　150
18.2.2　深度優(yōu)先搜索解法　151
18.2.3　并查集解法　152
第19章　數(shù)據(jù)結(jié)構(gòu)與算法面試
真題實(shí)戰(zhàn)　153
19.1　實(shí)例1：文件系統(tǒng)　　153
19.1.1　關(guān)于數(shù)據(jù)結(jié)構(gòu)的探討　154
19.1.2　面試題考查點(diǎn)　156
19.1.3　完整代碼　156
19.2　實(shí)例2：最長有效詞　　157
19.2.1　找到更快的解決方案　158
19.2.2　基于存儲(chǔ)/緩存的解決
方案　159
19.2.3　面試題考查點(diǎn)　161
19.3　實(shí)例3：圓圈組　　161
19.3.1　圓圈組的個(gè)數(shù)　163
19.3.2　最大的k個(gè)圓圈組　163
第四部分　系統(tǒng)設(shè)計(jì)
第20章　系統(tǒng)設(shè)計(jì)理論　166
20.1　設(shè)計(jì)步驟　　166
20.1.1　描述使用場景、約束和
假設(shè)　166
20.1.2　構(gòu)建高層設(shè)計(jì)　166
20.1.3　設(shè)計(jì)核心組件　167
20.1.4　擴(kuò)展設(shè)計(jì)　169
20.2　域名系統(tǒng)　　171
20.3　負(fù)載均衡器　　172
20.4　分布式緩存系統(tǒng)　　173
20.5　哈希一致性　　176
第21章　系統(tǒng)設(shè)計(jì)實(shí)戰(zhàn)　178
21.1　設(shè)計(jì)分布式緩存系統(tǒng)　　178
21.1.1　緩存無效　178
21.1.2　緩存逐出策略　179
21.1.3　設(shè)計(jì)分布式鍵值緩存
系統(tǒng)　180
21.2　設(shè)計(jì)網(wǎng)絡(luò)爬蟲系統(tǒng)　　181
21.2.1　架構(gòu)設(shè)計(jì)　181
21.2.2　爬蟲服務(wù)　181
21.2.3　處理重復(fù)鏈接　183
21.2.4　更新爬網(wǎng)結(jié)果　184
21.2.5　可擴(kuò)展性設(shè)計(jì)　184
21.3　TinyURL的加密與解密　　185
21.3.1　系統(tǒng)的要求和目標(biāo)　185
21.3.2　容量估算和約束　185
21.3.3　系統(tǒng)API　186
21.3.4　核心算法設(shè)計(jì)　187
21.3.5　數(shù)據(jù)庫設(shè)計(jì)　187
21.3.6　數(shù)據(jù)分區(qū)和復(fù)制　188
21.3.7　緩存　188
21.3.8　負(fù)載均衡器　189
21.4　設(shè)計(jì)自動(dòng)補(bǔ)全功能　　189
21.4.1　基本系統(tǒng)設(shè)計(jì)與算法　190
21.4.2　主數(shù)據(jù)結(jié)構(gòu)　191
21.4.3　優(yōu)化設(shè)計(jì)　192
21.5　設(shè)計(jì)新聞動(dòng)態(tài)功能　　195
21.6　設(shè)計(jì)X（Twitter）應(yīng)用　　198
21.7　設(shè)計(jì)Uber/Lyft應(yīng)用　　203
第22章　多線程編程　206
22.1　多線程面試問題　　206
22.2　實(shí)例1：形成水分子　　207
22.3　實(shí)例2：打印零、偶數(shù)、
奇數(shù)　　208
第23章　設(shè)計(jì)機(jī)器學(xué)習(xí)系統(tǒng)　210
23.1　機(jī)器學(xué)習(xí)的基礎(chǔ)知識　　210
23.1.1　什么是機(jī)器學(xué)習(xí)　210
23.1.2　為什么使用機(jī)器學(xué)習(xí)　211
23.1.3　監(jiān)督學(xué)習(xí)和無監(jiān)督學(xué)習(xí)　212
23.1.4　分類模型和回歸模型　213
23.1.5　轉(zhuǎn)換問題　214
23.1.6　關(guān)鍵數(shù)據(jù)　214
23.1.7　機(jī)器學(xué)習(xí)工作流程　215
23.1.8　欠擬合和過擬合　216
23.1.9　偏差和方差　217
23.2　機(jī)器學(xué)習(xí)的進(jìn)階知識　　220
23.2.1　處理不平衡的二進(jìn)制
分類　220
23.2.2　高斯混合模型和K均值
的比較　221
23.2.3　梯度提升　221
23.2.4　決策樹的約束　223
23.2.5　加權(quán)更新　223
23.2.6　隨機(jī)梯度提升　223
23.2.7　懲罰性學(xué)習(xí)　224
23.3　機(jī)器學(xué)習(xí)面試　　224
23.3.1　機(jī)器學(xué)習(xí)面試考查點(diǎn)　224
23.3.2　機(jī)器學(xué)習(xí)面試的思路　226
23.4　實(shí)例1：搜索排名系統(tǒng)　　227
23.4.1　題目解讀　227
23.4.2　指標(biāo)分析　228
23.4.3　架構(gòu)　229
23.4.4　結(jié)果選擇　231
23.4.5　訓(xùn)練數(shù)據(jù)生成　237
23.4.6　排名　238
23.4.7　篩選結(jié)果　240
23.5　實(shí)例2：Netflix電影推薦
系統(tǒng)　　242
23.5.1　題目解讀　242
23.5.2　指標(biāo)分析　244
23.5.3　架構(gòu)　246
23.5.4　特征工程　247
23.5.5　候選電影的產(chǎn)生　250
23.5.6　訓(xùn)練數(shù)據(jù)生成　252
23.5.7　排名　253