一本影响了全球数百万程序员的求职面试宝典，Amazon超级畅销书，持续销售近10年
授人以鱼，全面讲解程序员面试时需要掌握的各种编程必备知识和技巧；授人以渔，针对来自全球顶尖IT企业的极具代表性的面试题给出了解答思路，并揭示了这些企业的面试过程

程序员面试攻略（原书第3版）
Programming Interviews Exposed
Secrets to Landing Your Next Job
Third Edition
（美） John Mongan　Eric Giguère　Noah Kindler　著　李秉义　译

封底
在任何行业，无论是对于企业还是求职者，面试都是非常重要的一件事，软件行业也不例外。求职面试是一门大学问，程序员在应聘软件开发相关的工作时，要想轻松通过企业的面试并获得企业的青睐，除了要有过硬的技术本领外，还需要掌握求职面试的相关技巧。目前市面上关于程序员求职面试的书已经非常多，但是大多数书都仅限于面试题的收集和解析，旨在让程序员通过熟记一些常见题目的解答方法来应对企业在面试时可能提出的各种技术问题。事实证明，这种方法的效果非常有限，因为不同的企业所考查的重点不一样，企业面试的题目也在不断变化。
本书力争从内容组织和写作方式上避免这些问题，与其他同类书相同的地方是，本书也对程序员必备的软件开发技术进行了详细讲解；与同类书不一样的地方是，本书重在解题方法和思想上给读者启发，举一反三。本书还有一个特点——实用性很强，如果你对本书钻研得越深，收获将会越大。

作者简介
John Mongan　
天才程序员，专注于超级计算机的研究，在软件开发方面拥有丰富经验，精通C/C++、Java语言。在软件测试技术方面拥有多个专利。曾在多家软件公司和制药公司从事职业顾问工作。拥有斯坦福大学学士学位和加州大学圣地亚哥分校硕士和博士学位。目前在加州大学圣地亚哥分校作为常驻放射线学者开展医药信息学方面的研究。
Eric Giguère　
资深软件工程师，就职于Google，拥有数十年软件开发经验，精通C/C++、Java、BASIC语言。拥有滑铁卢大学计算机科学的BMath和MMath学位。著有多本编程类书籍。
Noah Kindler　
资深软件工程师，安全技术公司Avira技术副总裁。领导了多个软件产品的设计与开发，其领导的产品的用户数超过1亿。

译者简介
李秉义　
资深软件工程师，拥有丰富的软件开发经验。目前就职于腾讯公司，负责软件开发。重点关注事务处理、分布式存储、x86体系结构、Linux以及MySQL的实现。

我们首先要告诉你的最重要的事情与第1 版相同：你对本书钻研得越深，收获就越大。如果你只是泛泛地阅读本书，你会学到一些东西，但是如果在看答案前先自己尝试解决问题，那么你会收获更多。本书第1 版出版已经超过十年了，这就是说，许多我们必须告诉你的事情已经改变，因此需要有个机会来改编本书。
　　第3 版进行了最大程度的更新。除了对前一版进行改编、扩展以及更新，还增加了关于排序和设计模式这些重要的主题。本书对非编程部分的内容也进行了改编，以反映如今就业市场的现实。所有这些我们都像前一版一样，保持容易理解的风格和循序渐进的思考过程。
　　样例代码大部分采用C、C++ 或Java ，但在大多数情况下数据结构和算法才是重点，使用什么语言实现是次要的。所有的样例对于一个有经验的程序员来说应该都是很容易理解的。
　　我们中的一员（Eric ）最近通过了他梦想中的Google 公司职位的面试，这增加了他对于程序设计面试的认识，并将其收获反映在了这一版中。
　　我们希望你喜欢第3 版，并且希望对你获得自己喜欢的职位有所帮助。我们非常希望听到你关于本书的想法以及你的面试经验。你可以通过authors@piexposed.com 与我们联系。访问本书的官方网站：http://www.piexposed.com 可以获得最新的更新以及更多信息。
第1 版前言
　　如果你像我们一样，通常就不会读前言。但这本书的前言很有用，因此希望你能破例一次好好读一下。如果你对前言确实不感兴趣，我们希望你能看完下面这句话：你对本书钻研得越深，收获就越大。如果你只是泛泛地阅读本书，你会学到一些东西，但是如果在看答案之前先自己尝试解决问题，那么你会收获更多。
　　当你应聘一份程序设计、软件开发或技术咨询方面的工作时，雇主几乎总是会安排一次面试来考察你的程序设计能力。我们写作本书的目的就是希望能够帮助大家顺利地通过这类面试。程序设计面试的目的是为了考察应聘者的程序设计水平和动手能力，其过程与传统意义上的求职面试并没有多少相似之处，所以传统的应聘秘笈和面试技巧在这里并没有多大用处。程序设计面试题以程序设计问题、智力难题以及各种与计算机有关的技术为主。本书将对这些常见的程序设计面试题进行讨论，并通过一些取材真实的面试题向大家展示如何才能最好地回答这些问题。
　　看到这里，你可能会产生这样的疑问：作为本书的作者，我们都是些什么人？是谁让我们写这本书的？我们两人都是刚毕业不久的研究生，在过去的几年里，我们参加了许多场面试。从老牌大公司的技术咨询职位到新兴公司的编写设备驱动程序的职位，我们面试过的工作岗位可以说五花八门，这本书就是我们根据自己亲身参加过的各种面试（有成功也有失败）总结出来的。我们认为，这是写作本书的基础。说实话，我们并不清楚负责招聘工作的人力资源部门主管对程序设计面试工作都有哪些想法，我们也不清楚猎头公司将依据什么样的标准来评估应聘人员在程序设计面试中的表现。但在读完本书之后，相信大家都会对美国顶尖的软件和计算机公司里的程序设计面试情况有一个比较实际的了解，并知道自己应该去做些什么来赢得自己想要的那份工作。
注意
　　根据自己的亲身经历，我们认为现在的程序设计面试工作还有许多地方需要改进。现在的做法过于偏重考察应聘人员解答智力难题或者类似问题的能力，而忽视了对其知识面和知识深度的考察，因此很多在软件行业中取得成功所必须具备的重要素质都无法得到准确衡量和评估。
　　需要特别说明的是，本书中的面试题目没有一道是我们虚构出来的，这些题目全部来自于我们此前参加过的面试。换句话说，类似的题目类型和难度很可能会出现在你今后参加的某次程序设计面试中。但大家同时也要明白，这本书里的问题只是程序设计面试中一些比较有代表性的题目，而不是一个包罗万象的习题集。如果希望靠死记硬背本书的例题和答案来通过程序设计面试，就很可能弄巧成拙。在面试中你可能会遇到这本书里的问题，但你不能抱有这样的幻想。程序设计面试题本来就是千变万化的，而一位聪明的面试官在看过本书之后，肯定不会再用本书中的题目。可话又说回来，程序设计面试题范围内的类型也就那么多，想变化也变化不到哪里去。只要你不是死抠本书中给出的例题，而是对它们所代表的试题类型进行研究，那么无论在程序设计面试中遇到什么样的题目，你肯定都能应付自如。
　　为了帮助大家提高解决问题的能力，我们采用了一种循序渐进的办法。首先，根据实际情况，我们会在给出面试题之前对有关的重要概念进行复习。其次，我们会把解决问题的整个思路向大家解释清楚，而不是简单地直接给出问题的答案。我们发现，从例题的使用方面来讲，本书以外的其他教科书或习题集几乎全都采用了另一种套路：先列出一个问题，接着马上给出答案，然后再解释那个答案为什么是正确的。以我们个人的体会来说，这种套路往往不能给你以最大的帮助：你能够看懂某个具体的答案，并知道它为什么是正确的，但很难了解和把握作者得出有关答案的思路，不容易在遇到与例题类似的问题时做出正确的分析和判断。为了避免上述弊病，本书采用了一种循序
　　渐进的解题方法，而我们希望本书中的解题思路不仅能够让大家知道什么是正确的解决方案，还能让大家明白怎样才能得出正确的解决方案。
　　只看不动手是学不到真本领的。如果你想从本书中得到的收获最大，就必须亲自动手去尝试解决书中的每一道题。我们建议大家采用下面的学习方法：
　　（1）看过题目之后，先把书放在一边，自己动手去寻找答案。
　　（2）如果你中途卡住了，再回过头来研究书中的解决方案。为了让大家开动脑筋，这本书里所有例题的答案都安排在有关内容的最末尾，所以你完全不必担心我们会提前“泄密”，让大家“意外地”看到答案。
　　（3）在看过足够多的内容并得到足够多的提示之后，你应该再次把本书放在一边，继续开动脑筋。
　　（4）如此重复，直到彻底解决某个问题为止。
　　你通过自己的努力而得出的解决方案越多，对有关问题的理解也就越透彻。这种学习方法还有另外一个好处，那就是它与程序设计面试的实际过程非常相似：你必须完全依靠自己来解决面试问题，但在需要的时候，面试官会给出必要的提示。
程序设计是一种难度极大的技术性艺术，只通过一本书就把计算机科学和程序设计工作所涉及的各种细节全都介绍给大家是根本不可能的。因此阅读本书需要有一定基础。我们希望你的计算机知识不低于大学计算机系一年级或二年级学生的水平。具体地说，我们希望你能够熟练地使用C 语言进行编程，有使用C++ 或Java 进行面向对象编程的经验，了解计算机体系结构和计算机科学理论方面的基础内容。这是参加程序开发工作最小的要求，所以大多数面试官都会有类似的预期。如果发现自己在上述几个方面有所欠缺，请务必在找工作和参加程序设计面试之前把功课补上。
　　在本书的读者中，肯定会有很多人在计算机方面的学识与经验大大超出我们刚才提出的最小要求。如果你就是其中一员，那么你可能对本书中的一些高级主题，比如数据库、图形处理、并发计算以及Perl 语言等更感兴趣。但千万不要因为自己的经验比较丰富就忽视了基础性的概念和试题。不管你的简历写得多好，面试官仍会从最基本的问题开始提问。
　　我们已经尽了最大的努力来保证这本书里的信息是正确无误的。所有的程序代码都经过了编译和测试。但就与读者在你们自己的程序设计工作中遇到的情况一样，程序设计漏洞和错误是在所难免的。一旦发现或者得知此类错误，我们会立刻把它们公布在http://www.piexposed.com 上。
　　我们相信，在你寻找新工作时，本书对你一定有所帮助。同时，我们还希望本书中的面试题目分析和解决方案能够对你找工作有所启发。如果你想把你的读后感、对每个问题的具体看法，或最近看到的某个程序设计面试问题告诉我们，我们将非常欢迎。我们的电子邮件是：authors@piexposed.com 。
　　预祝大家都能找到一份满意的工作！

计算机\程序设计

在任何行业，无论是对于企业还是求职者，面试都是非常重要的一件事，软件行业也不例外。求职面试是一门大学问，程序员在应聘软件开发相关的工作时，要想轻松通过企业的面试并获得企业的青睐，除了要有过硬的技术本领外，还需要掌握求职面试的相关技巧。目前市面上关于程序员求职面试的书已经非常多，但是大多数书都仅限于面试题的收集和解析，旨在让程序员通过熟记一些常见题目的解答方法来应对企业在面试时可能提出的各种技术问题。事实证明，这种方法的效果非常有限，因为不同的企业所考查的重点不一样，企业面试的题目也在不断变化。
本书力争从内容组织和写作方式上避免这些问题，与其他同类书相同的地方是，本书也对程序员必备的软件开发技术进行了详细讲解；与同类书不一样的地方是，本书重在解题方法和思想上给读者启发，举一反三。本书还有一个特点——实用性很强，如果你对本书钻研得越深，收获将会越大。

（美） John Mongan　Eric Giguère　Noah Kindler 著：暂无简介

李秉义 译：暂无简介

顶级软件公司的程序设计面试通常是很艰难的，即使是非常优秀的程序员，如果没有经历过这类面试并进行充分的准备，也很难通过。拥有扎实的编程技能和丰富的计算机基础知识通常还不足以让你轻松通过这类面试，你还需要掌握面试中的沟通技巧与答题技巧。这样才能在有限的面试时间中让面试官了解你的真实能力。
　　本书深入探究了顶级软件公司的程序设计面试过程，并且对可能出现的面试题目进行了分类汇总，引导你学习解决各类问题的方法。而不是通过罗列大量面试问题，通过死记硬背来教你准备程序设计面试。此外，由于程序设计题目千变万化，通过死记硬背不能给你通过面试带来实质性的帮助。
　　努力学完本书，你将能够掌握顶级软件公司的面试过程，在面对各类面试问题时能够迅速找到切入点，从容应对，并在面试过程中将自己的能力充分展示给面试官。
　　感谢机械工业出版社的编辑在本书的翻译工作中所付出的努力。尽管译者在翻译时反复推敲，查阅了大量资料以确保专业术语的翻译准确，但译文中难免还有不当之处，敬请批评指正。

译者序
前言
致谢
技术编辑简介
第0 章　引言 ··········· 1
第1 章　求职之前 ·· 4
1.1 了解你自己 ····· 4
1.2 了解市场 ········· 6
1.2.1 基本的市场信息 · 6
1.2.2 外包怎么样 ········· 7
1.3 培养市场需要的技能 ····· 8
1.4 把事情做好 · 8
1.5 管理网上个人资料 ········· 9
1.6 本章小结 ··· 10
第2 章　求职过程 ················ 11
2.1 寻找公司并进行联系 ··· 11
2.1.1 寻找公司 ··········· 11
2.1.2 获得推荐 ··········· 12
2.1.3 与猎头打交道 ··· 12
2.1.4 直接与公司联系 ··················· 13
2.1.5 招聘会 ··············· 13
2.2 面试过程 ··· 14
2.2.1 筛选面试 ··········· 14
2.2.2 现场面试 ··········· 14
2.2.3 衣着 ··················· 15
2.3 招聘人员的角色 ··········· 15
2.4 工作要约和协商 ··········· 16
2.4.1 应对招聘人员的压力 ············ 16
2.4.2 薪资协商 ··········· 17
2.4.3 接受要约与拒绝要约 ············ 18
2.5 本章小结 ··· 18
第3 章　编程问题的解答思路 ··············· 19
3.1 面试过程 ··· 19
3.1.1 面试场景 ··········· 19
3.1.2 面试问题 ··········· 19
3.1.3 使用哪种编程语言 ··············· 20
3.1.4 互动是关键 ······· 20
3.2 解决问题 ··· 21
3.2.1 基本步骤 ··········· 21
3.2.2 当你被卡住时 ··· 23
3.3 分析解决方案 ··············· 24
3.3.1 大O 分析法实战··················· 24
3.3.2 大O 分析法为何有效 ··········· 25
3.3.3 最好情况、平均情况和最坏情况 ··················· 26
3.3.4 优化与大O 分析法 ··············· 26
3.3.5 如何进行大O 分析法 ··········· 27
3.3.6 哪个算法更好 ··· 27
3.3.7 内存占用分析 ··· 28
3.4 本章小结 ··· 28
第4 章　链表 ····· 30
4.1 为什么是链表 ··············· 30
4.2 链表的种类 ··················· 30
4.2.1 单链表 ··············· 31
4.2.2 双向链表 ··········· 32
4.2.3 循环链表 ··········· 33
4.3 基本链表操作 ··············· 33
4.3.1 追踪头元素 ······· 33
4.3.2 遍历一个链表 ··· 34
4.3.3 插入和删除元素 ··················· 35
4.4 链表问题 ··· 36
4.4.1 栈的实现 ··········· 37
4.4.2 维护链表尾指针 ··················· 41
4.4.3 removeHead 中的bug ··········· 46
4.4.4 链表中的倒数第m 个元素 ··· 47
4.4.5 链表展平 ··········· 50
4.4.6 取消链表展平 ··· 53
4.4.7 Null 或循环 ······· 55
4.5 本章小结 ··· 57
第5 章　树和图 ·········· 58
5.1 树 ············· 58
5.1.1 二叉树 ··············· 60
5.1.2 二叉搜索树 ······· 61
5.1.3 堆 ············· 63
5.1.4 常见搜索 ··········· 63
5.1.5 遍历 ··················· 64
5.2 图 ·············· 64
5.3 树与图的问题 ··············· 65
5.3.1 树的高 ··············· 65
5.3.2 前序遍历 ··········· 66
5.3.3 非递归前序遍历 ··················· 67
5.3.4 最近共同祖先 ··· 69
5.3.5 二叉树转堆 ······· 71
5.3.6 非平衡二叉搜索树 ··············· 73
5.3.7 凯文· 培根的六度空间 ········· 74
5.4 本章小结 ··· 78
第6 章　数组和字符串 ········ 79
6.1 数组 ·········· 79
6.1.1 C 和C++ ··········· 80
6.1.2 Java　··········81
6.1.3 C# ··········· 81
6.1.4 JavaScript ········· 81
6.2 字符串 ······· 82
6.2.1 C ···· 83
6.2.2 C++ ·········· 83
6.2.3 Java ·········· 83
6.2.4 C# ·· 84
6.2.5 Javascript ··········· 84
6.3 数组和字符串问题 ······· 85
6.3.1 找到第一个不重复的字符 ···· 85
6.3.2 删除指定的字符 ··················· 88
6.3.3 反转单词 ··········· 90
6.3.4 整数/ 字符串转换 ················ 94
6.4 本章小结 ············· 99
第7 章　递归 ············· 100
7.1 理解递归 ··········· 100
7.2 递归问题 ··········· 103
7.2.1 二分搜索 ········· 103
7.2.2 字符串的全排列 ················· 105
7.2.3 字符串的全组合 ················· 108
7.2.4 电话按键单词 · ··········110
7.3 本章小结 · ··········115
第8 章　排序 ············· 116
8.1 排序算法 · ··········116
8.1.1 选择排序 ········· 117
8.1.2 插入排序 ········· 118
8.1.3 快速排序 ········· 119
8.1.4 归并排序 ········· 120
8.2 排序问题 ··········· 122
8.2.1 最好的排序算法 ················· 122
8.2.2 稳定的选择排序 ················· 125
8.2.3 多键排序 ········· 127
8.2.4 使一个排序稳定 ················· 128
8.2.5 最优化快速排序 ················· 129
8.2.6 煎饼排序 ········· 132
8.3 本章小结 ··········· 134
第9 章　并发 ··· 135
9.1 线程的基本概念 ········· 135
9.1.1 线程 ················· 135
9.1.2 系统线程与用户线程 ·········· 136
9.1.3 监视器与信号量 ················· 136
9.1.4 死锁 ················· 137
9.1.5 线程示例 ········· 137
9.2 并发问题 · ··········140
9.2.1 忙等待 ············· 140
9.2.2 生产者/ 消费者 ·················· 142
9.3 哲学家就餐 ················ 144
9.4 本章小结 ··········· 147
第10 章　面向对象编程 ··· 148
10.1 基础知识 ··················· 148
10.1.1 类与对象 ······· 148
10.1.2 继承与多态 ··· 149
10.2 构造函数与析构函数 ··················· 150
10.3 面向对象编程问题 ··· 151
10.3.1 接口与抽象类 ··················· 151
10.3.2 虚方法 ··········· 152
10.3.3 多重继承 ······· 154
10.4 本章小结 ··················· 155
第11 章　设计模式 ············ 156
11.1 什么是设计模式 ······· 156
11.1.1 为什么使用设计模式 ········ 156
11.1.2 面试中的设计模式 ············ 157
11.2 常见的设计模式 ······· 157
11.2.1 创建型模式 ··· 157
11.2.2 行为型模式 ··· 160
11.2.3 结构型模式 ··· 160
11.3 设计模式问题 ··········· 161
11.3.1 实现单例模式 ··················· 161
11.3.2 装饰模式与继承 ················ 163
11.3.3 高效的观察者更新 ············ 164
11.4 本章小结 ··················· 164
第12 章　数据库 ················ 165
12.1 数据库基础 ··············· 165
12.1.1 关系数据库 ··· 165
12.1.2 SQL ··············· 166
12.1.3 数据库事务 ··· 169
12.2 数据库问题 ··············· 170
12.2.1 简单SQL ······· 170
12.2.2 公司和员工数据库············ 171
12.2.3 不使用汇总返回最大值 ···· 173
12.2.4 三值逻辑 ······· 174
12.3 本章小结 ··················· 175
第13 章　图形学和位操作 ··················· 176
13.1 图形学 ··· 176
13.2 位操作 ··· 177
13.2.1 二进制的补码表示············ 177
13.2.2 位操作 ··········· 178
13.2.3 利用移位进行优化············ 179
13.3 图形学问题 ··············· 179
13.3.1 八分之一圆 ··· 179
13.3.2 矩形重叠 ······· 181
13.4 位处理问题 ··············· 184
13.4.1 大端序或小端序 ··············· 184
13.4.2 1 的个数 ········ 186
13.5 本章小结 ··················· 189
第14 章　计数、测量和排序难题 ······ 190
14.1 处理难题 ··················· 190
14.1.1 解决正确的问题 ··············· 191
14.1.2 不要被吓倒 ··· 192
14.1.3 当心简单的问题 ··············· 192
14.1.4 估算问题 ······· 193
14.2 智力难题 ··················· 193
14.2.1 统计打开的锁 ··················· 193
14.2.2 三个开关 ······· 195
14.2.3 过桥 ··············· 196
14.2.4 较重的弹珠 ··· 199
14.2.5 美国的加油站数量············ 202
14.3 本章小结 ··················· 203
第15 章　图形和空间方面的难题 ······ 204
15.1 先画下来 ··················· 204
15.2 图形和空间问题 ······· 205
15.2.1 船和码头 ······· 205
15.2.2 数立方体 ······· 207
15.2.3 狐狸与鸭子 ··· 210
15.2.4 燃烧导火索 ··· 212
15.2.5 躲避火车 ······· 213
15.3 本章小结 ··················· 214
第16 章　知识问题 ············ 215
16.1 准备······· 215
16.2 问题······· 216
16.2.1 C++ 与Java ··· 217
16.2.2 友元类 ··········· 217
16.2.3 参数传递 ······· 218
16.2.4 宏与内联函数 ··················· 219
16.2.5 继承 ··············· 220
16.2.6 垃圾收集 ······· 221
16.2.7 32 位与64 位应用程序 ····· 222
16.2.8 网络性能 ······· 223
16.2.9 网络应用程序安全············ 223
16.2.10 加密 ············· 225
16.2.11 散列表与二叉搜索树 ······ 226
16.3 本章小结 ··················· 226
第17 章　非技术问题 ······· 227
17.1 为什么要问非技术问题 ··············· 227
17.2 问题······· 228
17.2.1 你想从事哪方面的工作 ···· 228
17.2.2 你最喜欢哪一种编程语言 ··· 229
17.2.3 你的工作方式是怎样的 ···· 229
17.2.4 请谈一谈你的工作经历 ···· 230
17.2.5 你的职业目标是什么 ········ 230
17.2.6 你为什么要换工作············ 230
17.2.7 你希望拿多少报酬············ 231
17.2.8 你以前的薪酬是多少 ········ 233
17.2.9 我们为什么要雇你············ 233
17.2.10 你为什么想加入这家公司 ····· 234
17.2.11 你有什么问题想问我吗 ··· 234
17.3 本章小结 ··················· 234
附录A　如何编写简历 ······ 235
结束语 ················ 255