轻松拿捏大数据算法面试：典型算法面试题全解及面试指导

作　者：	杨国栋徐扬徐振超
出版社：	机械工业出版社
丛编项：
版权说明：	本书为公共版权或经版权方授权，请支持正版图书
标　签：	暂缺

ISBN	出版时间	包装	开本	页数	字数
未知	暂无	暂无	未知	0	暂无

作者简介

　　杨国栋“数据之力技术丛书”主任，前腾讯软件工程师。一直就职于头部互联网公司，从事大数据平台与基础架构相关工作，具有多年一线工作经验。《Apache Pulsar原理解析与应用实践》《大数据SQL优化：原理与实践》等书作者。徐扬PowerData社区骨干成员，某头部大厂算法工程师，从事多年算法研究工作，致力于通过算法优化和创新，解决实际业务场景中的数据处理与分析难题。徐振超“数据之力技术丛书”编委会成员，“数据极客圈”公众号/CSDN主理人。现任某头部互联网企业数据库技术生态研发工程师，专注数据库查询优化工作，具有丰富的实战经验。黄海军现任某头部互联网企业某头部数据库技术生态研发工程师，《数据微光》公众号主理人。深耕开源多年，聚焦技术生态构建与实战经验沉淀，致力于推进前沿技术在行业场景中的价值释放。罗富良现任上海某头部旅行公司数据开发工程师。从事离线数据仓库、实时数据仓库与湖仓一体化研发工作，在数仓开发方面有丰富的实践经验。赵思南现就职于某头部网络广告代理商公司，从事大数据平台与数据分析等相关工作，在大数据平台开发方面具有多年一线工作经验。活跃于多个社区，乐于知识分享。

内容简介

内容简介这是6位来自多个大厂的大数据工程师联合力扣撰写的，深度解读大数据算法面试母题的求职手册。本融合了几位作者总计数百次面试他人和被他人面试的经验，结合对大厂招聘的真实需求，深度解读精选自力扣的近百道具有代表性的算法题。这些题目覆盖了几乎所有大数据从业者需要掌握的算法题类型，它们有的来自力扣多年的专业沉淀，有的来自各家企业的真实招聘题库。各位作者从实际应用场景出发，解读每道题出现在面试中的底层逻辑，然后给出具体的解题思路和编程示例，并从时间复杂度和空间复杂度两个层面分析示例程序。第1章和第2章从数据结构这个层面解读数组、链表、字符串、哈希表、栈、队列、树和图，这是所有算法的基础，然后深入分析了排序、递归、分治、贪心、回溯算法以及动态规划等基础算法的母题。第3章和第4章则聚焦大数据领域，从计算与存储两个维度解读面试中常见的算法题，比如Top k问题、中位数问题、位图算法问题、有序哈希字典问题、树存储问题、索引设计问题、海量数据写入与存储问题等。第5章和第6章精选了多道来自真实面试的算法题进行精讲，并从如何高效刷题、如何准备面试两个层面给出精准指导。

图书目录

Contents　目　录

前言

第1章　基础数据结构1

1.1　数组1

1.1.1　两数之和—输入有序数组1

1.1.2　删除有序数组中的重复项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　快乐数23

1.4.2　找到所有数组中消失的数字24

1.4.3　最长连续序列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　排序数组的求解61

2.1.2　思维延展68

2.2　递归算法69

2.2.1　斐波那契数69

2.2.2　两两交换链表中的节点72

2.2.3　思维延展73

2.3　分治算法74

2.3.1　多数元素75

2.3.2　将有序数组转换为二叉

　　　搜索树77

2.3.3　最大子数组和79

2.3.4　排序链表81

2.3.5　思维延展84

2.4　贪心算法85

2.4.1　分发饼干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　岛屿数量96

2.5.4　n皇后98

2.5.5　思维延展101

2.6　动态规划101

2.6.1　爬楼梯102

2.6.2　不同路径104

2.6.3　编辑距离106

2.6.4　接雨水108

2.6.5　思维延展110

第3章　大数据量计算112

3.1　Top k问题112

3.1.1　前k个高频单词113

3.1.2　数组中的第k个最大元素116

3.1.3　思维延展—限制内存Top N118

3.2　中位数118

3.2.1　寻找两个正序数组的中位数119

3.2.2　数据流的中位数122

3.2.3　思维延展:如何从5亿个数

　　　中找出中位数125

3.3　位图算法131

3.3.1　只出现一次的数字131

3.3.2　丢失的数字133

3.3.3　思维延展:统计不同手机

　　　号码的个数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　快速查找树的父节点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　计数质数213

5.2　奇妙的数论题215

5.2.1　镜面反射215

5.2.2　n的第k个因子217

5.2.3　最简分数219

5.2.4　使数组可以被整除的最少

　　　删除次数221

5.3　灵活的数据结构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　连续时间问题243

5.5.2　时间间隔问题244

5.5.3　Top N问题245

5.5.4　用户留存率问题247

5.5.5　窗口函数问题248

第6章　面试准备指南250

6.1　算法刷题的重要性250

6.1.1　大数据时代的挑战251

6.1.2　算法对于大数据处理的作用251

6.2　大数据刷题技巧252

6.2.1　解决问题的方法论254

6.2.2　多种解法对比和分析的

　　　重要性255

6.2.3　多做题目多总结256

6.2.4　面试模拟和实战演练257

6.2.5　学会利用资源260

6.3　面试准备261

6.3.1　了解大数据职业方向261

6.3.2　不同职位对算法的要求262

6.4　面试技巧263

6.4.1　自信和积极的态度264

6.4.2　清晰的表达和逻辑思维265

6.4.3　如何回答算法问题和优化

　　　思路266

6.4.4　针对不熟悉的问题的应对

　　　策略26