正版新书]硅谷Python工程师面试指南 数据结构、算法与系统设计

前言

第一部分 面试流程

第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

（1）内容权威：谷歌面试官和OPPO高级研究总监联手打造。作者基于亲身经验，有的放矢地解析数据结构、算法和系统设计3大核心技能面，筛选硅谷及国内科技巨头面试真题
（2）质量可靠：西北工业大学教授、美国乔治亚大学教授、华为专家、谷歌专家推荐。本书不仅透彻讲解常见的Python技术核心，还强调了重要而易被忽视的系统设计类题目，
用丰富实例打造硅谷科技企业的Python面试秘籍。
（3）收获切实：通过阅读本书，你将：1）了解硅谷高科技公司以及国内科技大厂面试的流程；2）利用真题训练来巩固面试所需的基本技能；3）更好地准备科技大厂的面试，从而争取更高的待遇条件。