程序员面试金典(第6版·修订版)

第 一部分 求职准备 全面了解

第 1 章 面试之前 1

1.1 积累编程经验 1

1.2 写好简历 2

1.2.1 简历篇幅长度适中 2

1.2.2 工作经历 2

1.2.3 项目经历 2

1.2.4 软件和编程语言 3

1.2.5 提防（潜在的）污名 3

第 2 章 面试的流程 4

2.1 面试准备清单 4

2.1.1 你有哪些缺点 4

2.1.2 你应该问面试官哪些问题 4

2.2 掌握项目所用的技术 5

2.3 如何应对面试中的提问 5

2.3.1 正面应答，避免自大 5

2.*.* 省略细枝末节 6

2.3.3 多谈自己 6

2.3.4 回答条理清晰 6

2.4 自我介绍 7

2.4.1 结构 7

2.4.2 展示成功的点点滴滴 8

2.5 面试流程 8

2.5.1 国内企业的面试流程 9

2.5.2 国际企业面试的流程 11

2.6 面试成绩 13

第 3 章 技术面试题 14

3.1 准备事项 14

*.* 基础知识 14

*.*.1 核心数据结构、*法及概念 14

*.*.2 2 的幂表 15

3.3 解题步骤 15

3.3.1 认真听 16

3.*.* 画*例图 17

3.3.3 给出一*蛮力法 17

3.3.4 优化 17

3.3.5 梳理 18

3.3.6 实现 18

3.3.7 测试 19

3.4 优化和解题技巧 19

3.4.1 寻找 BUD 19

3.4.2 亲力亲为 22

3.4.3 化繁为简 23

3.4.4 由浅入深 23

3.4.5 数据结构头脑风暴法 24

3.5 可想象的极限运行时间 24

3.6 处理错误答案 27

3.7 做过的面试题 27

3.8 面试的“完美”语言 28

3.9 好代码的标准 29

第二部分 技术面试题目中的基础知识

第 4 章 大 O 33

4.1 时间复杂度 33

4.2 空间复杂度 35

4.3 删除常量 35

4.4 丢弃不重要的项 36

4.5 多项式*法：加与乘 37

4.6 分摊时间 37

4.7 log N 运行时间 38

4.8 递归的运行时间 38

4.9 例题分析 39

第 5 章 数组与字符串 52

5.1 散列表 52

5.2 ArrayList 与可变长度数组 53

5.3 StringBuilder 53

第 6 章 链表 55

6.1 创建链表 55

6.2 删除单向链表中的节点 56

6.3 “快行指针”技巧 56

6.4 递归问题 56

第 7 章 栈与队列 57

7.1 实现一*栈 57

7.2 实现一*队列 58

第 8 章 树与图 60

8.1 树的类型 60

8.1.1 树与二叉树 60

8.1.2 二叉树与二叉搜*树 61

8.1.3 平衡与不平衡 61

8.1.4 完整二叉树 61

8.1.5 满二叉树 62

8.1.6 完美二叉树 62

8.2 二叉树的遍历 62

8.3 二叉堆（小顶堆与大顶堆） 63

8.4 单词查找树（前序树） 64

8.5 图 65

8.5.1 邻接链表法 65

8.5.2 邻接矩阵法 66

8.6 图的搜* 66

8.6.1 深度优先搜* 67

8.6.2 广度优先搜* 67

8.6.3 双向搜* 68

第 9 章 位操作 69

9.1 手工位操作 69

9.2 位操作原理与技巧 69

9.3 二进制补码与负数 70

9.4 *术右移与逻辑右移 70

9.5 常见位操作：获取与设置数位 71

第 10 章 数学与逻辑题 73

10.1 素数 73

10.2 概率 75

10.3 总结规律和模式 76

第 11 章 面向对象设计 78

11.1 如何解答 78

11.2 设计模式 79

11.2.1 单例设计模式 79

11.2.2 工厂方法设计模式 79

第 12 章 递归与动态规划 81

12.1 解题思路 81

12.2 递归与迭代 81

12.3 动态规划及记忆法 82

第 13 章 系统设计与可扩展性 86

13.1 处理问题 86

1*.* 循环渐进的设计 87

13.3 逐步构建的方法：循序渐进 88

13.4 关键概念 88

13.5 系统设计要考虑的因素 90

13.6 实例演示 91

第 14 章 排序与查找 93

14.1 常见的排序*法 93

14.2 查找*法 95

第 15 章 数据库 97

15.1 SQL 语法及各类变体 97

15.2 规范化数据库和反规范化数据库 97

15.3 SQL 语句 97

15.4 小型数据库设计 99

15.5 大型数据库设计 100

第 16 章 C 和 C 101

16.1 类和继承 101

16.2 构造函数和析构函数 101

16.3 虚函数102

16.4 虚析构函数 103

16.5 默认值104

16.6 操作符重载 104

16.7 指针和引用 104

16.8 模板 105

第 17 章 Java 107

17.1 如何处理 107

17.2 重载与重写 107

17.3 集合框架 108

第 18 章 线程与锁 110

18.1 Java 线程 110

18.2 同步和锁 112

18.3 死锁及死锁的预防 114

第 19 章 测试 116

19.1 面试官想考查什么 116

19.2 测试现实生活中的事物 116

19.3 测试一套软件 117

19.4 测试一*函数 119

19.5 调试与故障排除 119

第三部分 经典题型 轻松拿捏

第 20 章 数组与字符串 121

20.1 判定字符是否 121

20.2 URL 化 122

20.3 回文串排列 123

20.4 字符串压缩 125

第 21 章 链表 128

21.1 返回倒数第 k *节点 128

21.2 链表求和 130

21.3 链表相交 132

21.4 环路检测 135

第 22 章 栈与队列 138

22.1 三合一 138

22.2 化栈为队 142

22.3 栈排序 143

第 23 章 树与图 145

23.1 特定深度节点链表 145

2*.* 后继者 146

23.3 编译顺序 147

23.4 **共同祖先 153

23.5 二叉搜*树序列 158

23.6 检查子树 160

23.7 随机节点 163

23.8 求和路径 166

第 24 章 位操作 171

24.1 插入 171

24.2 二进制数转字符串 172

24.3 下一*数 173

24.4 配对交换 177

第 25 章 数学与逻辑题 178

25.1 较重的药丸 178

25.2 篮球问题 178

25.3 大灾难 179

25.4 扔鸡蛋问题 181

25.5 有毒的汽水 183

第 26 章 面向对象设计 190

26.1 扑克牌 190

26.2 客服中心 192

26.3 聊天软件 194

26.4 环状数组 198

26.5 扫雷 200

26.6 散列表 205

第 27 章 递归与动态规划 207

27.1 三步问题 207

27.2 幂集 208

27.3 递归乘法 210

27.4 无重复字符串的排列组合 212

27.5 重复字符串的排列组合 215

27.6 括号 216

27.7 布尔运* 218

第 28 章 系统设计与可扩展性 221

28.1 网络爬虫 221

28.2 重复网址 222

28.3 缓存 222

28.4 销售排名 225

28.5 *人理财管理 228

第 29 章 排序与查找 231

29.1 变位词组 231

29.2 搜*轮转数组 232

29.3 排序集合的查找 233

29.4 失踪的整数 234

29.5 排序矩阵查找 238

29.6 峰与谷 241

第 30 章 数据库 244

30.1 多套公寓 244

30.2 连接 244

30.3 反规范化 245

30.4 设计分级数据库 246

第 31 章 C 和 C 248

31.1 后 K 行 248

31.2 反转字符串 249

31.3 散列表与 STL map 249

31.4 浅复制与深复制 250

31.5 volatile 关键字 251

31.6 分配内存 252

31.7 二维数组分配 253

第 32 章 Java 255

32.1 私有构造函数 255

32.2 final 们 255

32.3 泛型与模板 256

32.4 TreeMap、HashMap、LinkedHashMap 258

32.5 反射 259

32.6 lambda 表达式 259

第 33 章 线程与锁 261

33.1 进程与线程 261

3*.* 上下文切换 261

33.3 无死锁的类 262

33.4 顺序调用 266

33.5 FizzBuzz 268

第 34 章 测试 271

34.1 随机崩溃 271

34.2 无工具测试 271

第 35 章 中等难题 273

35.1 交换数字 273

35.2 交点 274

35.3 小差 276

35.4 整数的英文表示 277

35.5 运* 279

35.6 生存人数 282

35.7 部分排序 286

35.8 连续数列 288

35.9 模式匹配 290

35.10 交换求和 293

35.11 兰顿蚂蚁 296

35.12 1×5 *随机数方法中生成 7 *随机数 301

第 36 章 高难度题 304

36.1 不用加号的加法 304

36.2 消失的数字 305

36.3 字母与数字 307

36.4 2 出现的次数 310

36.5 主要元素 312

36.6 BiNode 315

36.7 小 k *数 318

36.8 多次搜* 323

36.9 消失的两*数字 327

36.10 单词转换 331

36.11 子矩阵 336

36.12 稀疏相似度 341

第 37 章 进阶话题 348

37.1 实用数学 348

37.1.1 整数 1 至 N 的和 348

37.1.2 2 的幂的和 349

37.1.3 对数的底 349

37.1.4 排列 349

37.1.5 组合 349

37.1.6 归纳证明 350

37.2 拓扑排序 350

37.3 Dijkstra *法 351

37.4 散列表冲突解决方案 353

37.4.1 使用链表连接数据 354

37.4.2 使用二叉搜*树连接数据 354

37.4.3 使用线性探测进行开放寻址 354

37.4.4 平方探测和双重散列 354

37.5 Rabin-Karp 子串查找 354

37.6 AVL 树 355

37.6.1 性质 355

37.6.2 插入操作 355

37.7 红黑树356

37.7.1 性质 357

37.7.2 为什么这样的树是平衡的 357

37.7.3 插入操作 357

37.8 MapReduce 360

37.9 补充学习内容 361