輕松拿捏大數(shù)據(jù)算法面試：典型算法面試題全解及面試指導

Contents　目　錄
前言
第1章　基礎數(shù)據(jù)結構1
1.1　數(shù)組1
1.1.1　兩數(shù)之和—輸入有序數(shù)組1
1.1.2　刪除有序數(shù)組中的重復項3
1.1.3　思維延展5
1.2　鏈表6
1.2.1　合并兩個有序鏈表7
1.2.2　相交鏈表8
1.2.3　思維延展11
1.3　字符串13
1.3.1　有效的字母異位詞13
1.3.2　重復的子字符串14
1.3.3　找出字符串中第一個匹配項
　　　的下標17
1.3.4　無重復字符的最長子串19
1.3.5　思維延展20
1.4　哈希表22
1.4.1　快樂數(shù)23
1.4.2　找到所有數(shù)組中消失的數(shù)字24
1.4.3　最長連續(xù)序列26
1.4.4　找到字符串中所有字母異
　　　位詞27
1.4.5　思維延展29
1.5　棧和隊列31
1.5.1　有效的括號31
1.5.2　每日溫度33
1.5.3　前k個高頻元素35
1.5.4　合并k個升序鏈表37
1.5.5　思維延展39
1.6　樹和二叉樹42
1.6.1　二叉樹的中序遍歷43
1.6.2　二叉樹的層序遍歷44
1.6.3　從前序與中序遍歷序列構造
　　　二叉樹47
1.6.4　二叉搜索樹的最近公共祖先49
1.6.5　思維延展51
1.7　圖53
1.7.1　島嶼的周長54
1.7.2　二進制矩陣中的最短路徑56
1.7.3　思維延展58
第2章　基礎算法60
2.1　排序算法60
2.1.1　排序數(shù)組的求解61
2.1.2　思維延展68
2.2　遞歸算法69
2.2.1　斐波那契數(shù)69
2.2.2　兩兩交換鏈表中的節(jié)點72
2.2.3　思維延展73
2.3　分治算法74
2.3.1　多數(shù)元素75
2.3.2　將有序數(shù)組轉換為二叉
　　　搜索樹77
2.3.3　最大子數(shù)組和79
2.3.4　排序鏈表81
2.3.5　思維延展84
2.4　貪心算法85
2.4.1　分發(fā)餅干85
2.4.2　加油站87
2.4.3　跳躍游戲90
2.4.4　思維延展91
2.5　回溯算法92
2.5.1　尋找子集93
2.5.2　全排列94
2.5.3　島嶼數(shù)量96
2.5.4　n皇后98
2.5.5　思維延展101
2.6　動態(tài)規(guī)劃101
2.6.1　爬樓梯102
2.6.2　不同路徑104
2.6.3　編輯距離106
2.6.4　接雨水108
2.6.5　思維延展110
第3章　大數(shù)據(jù)量計算112
3.1　Top k問題112
3.1.1　前k個高頻單詞113
3.1.2　數(shù)組中的第k個最大元素116
3.1.3　思維延展—限制內存Top N118
3.2　中位數(shù)118
3.2.1　尋找兩個正序數(shù)組的中位數(shù)119
3.2.2　數(shù)據(jù)流的中位數(shù)122
3.2.3　思維延展:如何從5億個數(shù)
　　　中找出中位數(shù)125
3.3　位圖算法131
3.3.1　只出現(xiàn)一次的數(shù)字131
3.3.2　丟失的數(shù)字133
3.3.3　思維延展:統(tǒng)計不同手機
　　　號碼的個數(shù)136
第4章　樹與存儲結構138
4.1　有序哈希字典問題138
4.1.1　排序鏈表與哈希字典138
4.1.2　樹形結構與哈希字典150
4.1.3　自平衡的樹形結構AVL樹153
4.1.4　紅黑樹159
4.2　樹的存儲問題161
4.2.1　二叉樹的序列化問題162
4.2.2　快速查找樹的父節(jié)點165
4.2.3　持久化的快速查找樹167
4.2.4　線段樹170
4.3　索引設計173
4.3.1　B樹174
4.3.2　更快排序的樹—B+樹178
4.3.3　空間索引問題180
4.3.4　R樹185
4.4　海量寫入的存儲設計192
4.4.1　LSM樹192
4.4.2　Bloom Filter201
第5章　面試真題211
5.1　關鍵的位運算211
5.1.1　顛倒二進制位212
5.1.2　計數(shù)質數(shù)213
5.2　奇妙的數(shù)論題215
5.2.1　鏡面反射215
5.2.2　n的第k個因子217
5.2.3　最簡分數(shù)219
5.2.4　使數(shù)組可以被整除的最少
　　　刪除次數(shù)221
5.3　靈活的數(shù)據(jù)結構223
5.3.1　并查集類算法223
5.3.2　單調棧226
5.3.3　位圖229
5.3.4　LRU緩存231
5.4　逃不過的算法題234
5.4.1　模擬題234
5.4.2　前綴和計算236
5.4.3　隨機化239
5.5　必知必會的SQL算法242
5.5.1　連續(xù)時間問題243
5.5.2　時間間隔問題244
5.5.3　Top N問題245
5.5.4　用戶留存率問題247
5.5.5　窗口函數(shù)問題248
第6章　面試準備指南250
6.1　算法刷題的重要性250
6.1.1　大數(shù)據(jù)時代的挑戰(zhàn)251
6.1.2　算法對于大數(shù)據(jù)處理的作用251
6.2　大數(shù)據(jù)刷題技巧252
6.2.1　解決問題的方法論254
6.2.2　多種解法對比和分析的
　　　重要性255
6.2.3　多做題目多總結256
6.2.4　面試模擬和實戰(zhàn)演練257
6.2.5　學會利用資源260
6.3　面試準備261
6.3.1　了解大數(shù)據(jù)職業(yè)方向261
6.3.2　不同職位對算法的要求262
6.4　面試技巧263
6.4.1　自信和積極的態(tài)度264
6.4.2　清晰的表達和邏輯思維265
6.4.3　如何回答算法問題和優(yōu)化
　　　思路266
6.4.4　針對不熟悉的問題的應對
　　　策略26