程序员面试金典（第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

　　盖尔·拉克曼·麦克道尔，CareerCup创立人兼CEO，是一位软件工程师，曾在微软、苹果与谷歌任职。她曾经顺利通过了微软、谷歌、苹果、IBM、高盛等多家名企极其严苛的面试过程，工作以后，她又成为一位出色的面试官，在谷歌任职期间，她还是谷歌招聘委员会成员，积累了相当丰富的面试经验。除此书外，还著有《产品经理面试宝典》《金领简历：敲开苹果、微软、谷歌的大门》。

　　本书是原谷歌资深面试官的经验之作，紧扣程序员面试环节，全面而详尽地介绍了程序员要为面试做哪些准备以及如何应对面试。主要内容涉及面试的流程解析、面试准备工作，以及多家知名公司的面试题目及详解。修订版特别结合国内科技公司的近况，修订了上一版中的一些问题，增添了国内科技公司的面试流程与注意事项。面试题目方面结合近年国内科技公司的考查重点，整合了原有的内容，围绕考核知识点精选了 100 多道题目，详细讲解了相关的*法策略。 本书适合程序开发人员和想要了解相关内容的学生阅读。