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

《程序员面试金典》是一本硅谷互联网公司技术面试的经典图书，被誉为程序员面试“”。作者是原谷歌zi深面试官，她结合自身丰富的面试经历，以及多年对互联网招聘行业形势的整理归纳，帮助许多想要加入Facebook、亚马逊、微软、苹果等互联网企业的求职者获得了心仪的工作机会。
《程序员面试金典》将帮助你磨练应聘的能力，你可以学会发现面试问题中的提示和隐藏细节，了解如何将一个面试问题分解为若干小的子问题，培养面试中克服障碍的技巧，温习经常会被问及的计算机科学核心概念，从而为真枪实弹的面试做好充足准备，现场发挥理想状态。

●189道难易不同的面试真题，每道问题都提供了详细解题过程
●通过解答提示模拟真实面试场景
●5个已被证实的解决算法问题的有效策略
●大O时间复杂度、数据结构和核心算法等基本话题讨论
●探秘IT名企如何招聘软件工程师
●准备面试中“软技能”的技巧，使自己行为得体
●从招聘公司和面试官角度，设计了面试与招聘流程的细节

本书是原谷歌面试官的经验之作，层层紧扣程序员面试的每一个环节，全面而详尽地介绍了程序员应当如何应对面试，才能在面试中脱颖而出。内容主要涉及面试流程解析，面试官的幕后决策及可能提出的问题，面试前的准备工作，对面试结果的处理，以及出自微软、苹果、谷歌等多家知名公司的189道编程面试题及详细解决方案。第6版修订了上一版中一些题目的解法，为各章新增了介绍性内容，加入了更多的算法策略，并增添了对所有题目的提示信息。

盖尔· 拉克曼·麦克道尔（Gayle Laakmann McDowell），CareerCup创始人兼CEO，是一位知名软件工程师，曾在微软、苹果与谷歌任职。早先，她自己是一位十分成功的求职者，通过了微软、谷歌、亚马逊、苹果、IBM、高盛等多家知名企业极其严苛的面试过程。工作以后，她又成为一位出色的面试官。在谷歌任职期间，她还是该公司有名的面试官及招聘委员会成员，其间阅人无数，积累了相当丰富的面试经验。除此书外，还著有《产品经理面试宝典》《金领简历：敲开苹果、微软、谷歌的大门》。

【译者简介】

刘博楠，软件工程师，毕业于哥伦比亚大学，现居美国纽约，就职于谷歌公司，从事云计算产品的研发工作，同时在纽约城市大学任兼职讲师。对分布式系统、云计算、数据库研发有着浓厚的兴趣。对超大规模系统架构设计、流程管理、高可用服务运维等领域也有涉猎。

赵鹏飞，毕业于西安电子科技大学，目前在蔚来汽车做开发工作。热爱技术，爱好开源，曾为流行开源项目OpenFeign贡献源码，近来专注于开源项目Spring及Spring Boot。热爱算法，一直活跃于leetcode、牛客网等算法网站。

李琳骁，主要从事嵌入式Linux内核/驱动开发，并关注IT、开放源码和安防监控等领域。业余时间以技术翻译为乐，翻译或参与翻译了《Linux命令详解手册》《编程人生》《编程大师访谈录》等图书。

漆犇，毕业于中国地质大学，拥有十余年软件开发、测试及流程管理经验，热衷翻译，已出版译作包括《Linux/Unix设计思想》《金领简历：敲开苹果、微软、谷歌的大门》等书。

第 1 章 面试流程 1
1.1  为什么  1
1.1.1  错过了优秀人才是可以的  2
1.1.2  解决问题的技能很宝贵  2
1.1.3  基础数据结构和算法知识很有用  2
1.1.4  白板让你专注于重要的事情  2
1.1.5  但这并不适用于每个人、每家公司、每种场合  3
1.2  面试问题的来源  3
1.3  一切都是相对的  3
1.4  常见问题  4
1.4.1  面试结束后没有立即收到回复，我是被拒了吗  4
1.4.2  被拒之后我还能重新申请吗  4
第  2 章 面试揭秘  5
2.1  微软面试  6
2.1.1  必备项  6
2.1.2  独特之处  6
2.2  亚马逊面试  6
2.2.1  必备项  7
2.2.2  独特之处  7
2.3  谷歌面试  7
2.3.1  必备项  8
2.3.2  独特之处  8
2.4  苹果面试  8
2.4.1  必备项  9
2.4.2  独特之处  9
2.5  Facebook面试  9
2.5.1  必备项  9
2.5.2  独特之处  10
2.6  Palantir面试  10
2.6.1  必备项  10
2.6.2  独特之处  10
第  3 章 特殊情况  11
3.1  有工作经验的求职者  11
3.2  测试人员和软件开发测试工程师  11
3.3  产品经理（项目经理）  12
3.4  开发主管与部门经理  13
3.5  创业公司  13
3.5.1  职位申请  14
3.5.2  签证与工作许可  14
3.5.3  简历筛选因素  14
3.5.4  面试流程  14
3.6  收购与“人才收购”  14
3.6.1  哪些创业公司需要进行并购面试，为什么  14
3.6.2  这些面试有多重要  15
3.6.3  哪些员工需要面试  15
3.6.4  如果面试表现不好会怎么样  15
3.6.5  最优秀和最差的员工或许会令你吃惊  16
3.6.6  被收购方的员工与一般求职者的标准一样吗  16
3.6.7  被收购员工对于收购、人才收购会如何反应  16
3.6.8  收购后的团队会经历什么  16
3.6.9  怎样为你的团队准备收购面试  16
3.7  面试官  17
3.7.1  不要问与本书完全相同的题目  17
3.7.2  问中等难题或者高难度题  17
3.7.3  使用多重障碍的题目  17
3.7.4  使用高难度题目，而不是艰深的基础知识  18
3.7.5  避免“吓人”的问题  18
3.7.6  提供正面鼓励  19
3.7.7  深究行为面试题  19
3.7.8  辅导求职者  19
3.7.9  如果求职者想保持安静，请满足  20
3.7.10  了解你的模式：完整性测试、质量测试、专业知识和代理知识  20
第  4 章 面试之前  22
4.1  积累相关经验  22
4.2  写好简历  23
4.2.1  简历篇幅长度适中  23
4.2.2  工作经历  23
4.2.3  项目经历  23
4.2.4  软件和编程语言  24
4.2.5  给母语为非英语的人及国际人士的建议  24
4.2.6  提防（潜在的）污名  24
4.3  准备流程图  25
第  5 章 行为面试题  28
5.1  面试准备清单  28
5.1.1  你有哪些缺点  28
5.1.2  你应该问面试官哪些问题  28
5.2  掌握项目所用的技术  29
5.3  如何应对  29
5.3.1  力求具体，切忌自大  29
5.3.2  省略细枝末节  30
5.3.3  多谈自己  30
5.3.4  回答条理清晰  30
5.3.5  行动是关键  31
5.3.6  故事的意义  31
5.4  自我介绍  32
5.4.1  结构  32
5.4.2  兴趣爱好  32
5.4.3  展示成功的点点滴滴  33
第  6 章 大Ο  34
6.1  打个比方  34
6.2  时间复杂度  34
6.2.1  大Ο、大θ和大Ω  35
6.2.2  最优、最坏和期望情况  35
6.3  空间复杂度  36
6.4  删除常量  36
6.5  丢弃不重要的项  37
6.6  多项式算法：加与乘  38
6.7  分摊时间  38
6.8  Log N运行时间  39
6.9  递归的运行时间  39
6.10  示例和习题  40
第  7 章 技术面试题  53
7.1  准备事项  53
7.2  必备的基础知识  53
7.2.1  核心数据结构、算法及概念  53
7.2.2  2的幂表  54
7.3  解题步骤  54
7.4  优化和解题技巧 1：寻找BUD  58
7.4.1  瓶颈  59
7.4.2  无用功  59
7.4.3  重复性工作  60
7.5  优化和解题技巧 2：亲力亲为  61
7.6  优化和解题技巧 3：化繁为简  62
7.7  优化和解题技巧 4：由浅入深  62
7.8  优化和解题技巧 5：数据结构头脑风暴法  63
7.9  可想象的极限运行时间  63
7.10  处理错误答案  66
7.11  做过的面试题  66
7.12  面试的“完美”语言  67
7.12.1  流行度  67
7.12.2  语言可读性  67
7.12.3  潜在问题  67
7.12.4  冗长  67
7.12.5  易用性  68
7.13  好代码的标准  68
7.13.1  多多使用数据结构  68
7.13.2  适当代码复用  69
7.13.3  模块化  70
7.13.4  灵活性和通用性  70
7.13.5  错误检查  71
7.14  不要轻言放弃  71
第  8 章 录用通知及其他注意事项  72
8.1  如何处理录用与被拒的情况  72
8.1.1  回复期限与延长期限  72
8.1.2  如何拒绝录用通知  72
8.1.3  如何处理被拒  72
8.2  如何评估录用待遇  73
8.2.1  薪酬待遇的考量  73
8.2.2  职业发展  73
8.2.3  公司稳定性  73
8.2.4  幸福指数  74
8.3  录用谈判  74
8.4  入职须知  75
8.4.1  制定时间表  75
8.4.2  打造坚实的人际网络  75
8.4.3  向经理寻求帮助  75
8.4.4  保持面试状态  75
第  9 章 面试题目  76
9.1  数组与字符串  76
9.1.1  散列表  76
9.1.2  ArrayList与可变长度数组  77
9.1.3  StringBuilder  77
9.2  链表  79
9.2.1  创建链表  79
9.2.2  删除单向链表中的节点  80
9.2.3  “快行指针”技巧  80
9.2.4  递归问题  81
9.3  栈与队列  82
9.3.1  实现一个栈  82
9.3.2  实现一个队列  83
9.4  树与图  85
9.4.1  树的类型  85
9.4.2  二叉树的遍历  87
9.4.3  二叉堆（小顶堆与大顶堆）  88
9.4.4  单词查找树（前序树）  89
9.4.5  图  90
9.4.6  图的搜索  91
9.5  位操作  94
9.5.1  手工位操作  95
9.5.2  位操作原理与技巧  95
9.5.3  二进制补码与负数  95
9.5.4  算术右移与逻辑右移  96
9.5.5  常见位操作：获取与设置数位  97
9.6  数学与逻辑题  99
9.6.1  素数  99
9.6.2  概率  101
9.6.3  大声说出你的思路  102
9.6.4  总结规律和模式  102
9.6.5  略作变通  103
9.6.6  触类旁通  104
9.7  面向对象设计  105
9.7.1  如何解答  105
9.7.2  设计模式  106
9.8  递归与动态规划  108
9.8.1  解题思路  109
9.8.2  递归与迭代  109
9.8.3  动态规划及记忆法  109
9.9  系统设计与可扩展性  114
9.9.1  处理问题  114
9.9.2  循环渐进的设计  114
9.9.3  逐步构建的方法：循序渐进  116
9.9.4  关键概念  116
9.9.5  系统设计要考虑的因素  118
9.9.6  人无完人，系统亦然  119
9.9.7  实例演示  119
9.10  排序与查找  121
9.10.1  常见的排序算法  121
9.10.2  查找算法  124
9.11  测试  126
9.11.1  面试官想考查什么  126
9.11.2  测试现实生活中的事物  127
9.11.3  测试一套软件  127
9.11.4  测试一个函数  129
9.11.5  调试与故障排除  129
9.12  C和C++  131
9.12.1  类和集成  131
9.12.2  构造函数和析构函数  131
9.12.3  虚函数  132
9.12.4  虚析构函数  133
9.12.5  默认值  134
9.12.6  操作符重载  134
9.12.7  指针和引用  134
9.12.8  模板  135
9.13  Java  136
9.13.1  如何处理  137
9.13.2  重载与重写  137
9.13.3  集合框架  138
9.14  数据库  139
9.14.1  SQL语法及各类变体  139
9.14.2  规范化数据库和非规范化数据库  139
9.14.3  SQL语句  140
9.14.4  小型数据库设计  141
9.14.5  大型数据库设计  142
9.15  线程与锁  143
9.15.1  Java线程  143
9.15.2  同步和锁  145
9.15.3  死锁及死锁的预防  148
9.16  中等难题  149
9.17  高难度题  152
第  10 章 题目解法  156
10.1  数组与字符串  156
10.2  链表  170
10.3  栈与队列  186
10.4  树与图  197
10.5  位操作  229
10.6  数学与逻辑题  240
10.7  面向对象设计  254
10.8  递归与动态规划  286
10.9  系统设计与可扩展性  313
10.10  排序与查找  332
10.11  测试  350
10.12  C和C++  354
10.13  Java  363
10.14  数据库  370
10.15  线程与锁  375
10.16  中等难题  388
10.17  高难度题  450
第  11 章 进阶话题  539
11.1  实用数学  539
11.1.1  整数1至N的和  540
11.1.2  2的幂的和  540
11.1.3  对数的底  542
11.1.4  排列  541
11.1.5  组合  541
11.1.6  归纳证明  541
11.2  拓扑排序  542
11.3  Dijkstra算法  543
11.4  散列表冲突解决方案  545
11.4.1  使用链表连接数据  545
11.4.2  使用二叉搜索树连接数据  546
11.4.3  使用线性探测进行开放寻址  546
11.4.4  平方探测和双重散列  546
11.5  Rabin-Karp子串查找  546
11.6  AVL树  547
11.6.1  性质  547
11.6.2  插入操作  547
11.7  红黑树  548
11.7.1  性质  549
11.7.2  为什么这样的树是平衡的  549
11.7.3  插入操作  549
11.8  MapReduce  551
11.9  补充学习内容  553
附录  A 代码库  554
附录  B 提示  560