高效制胜：程序员面试典型题解

异步图书 力扣官方作序推荐

卷积传媒

高效制胜：程序员面试典型题解

吴江 编著

人民邮电出版社

北京

图书在版编目（CIP）数据

高效制胜：程序员面试典型题解/吴江编著.--北京：人民邮电出版社，2021.7

ISBN 978-7-115-55198-6

Ⅰ. ①高… Ⅱ. ①吴… Ⅲ.①程序设计―资格考试―自学参考资料 Ⅳ. ①TP311.1

中国版本图书馆CIP数据核字（2021）第073436号

定价：79.90元

读者服务热线：(010)81055410　印装质量热线：(010)81055316

反盗版热线：(010)81055315

广告经营许可证：京东市监广登字20170147号

技术面试对于IT领域的求职者来说是一个关键环节。LeetCode（力扣）是许多求职者在准备面试或欲提高专业技术时常用的一个网站，求职者可通过合理且有效地运用网站上的题目资源更高效地准备面试。本书精选力扣上的几十道原题，涵盖求和问题、动态规划法、堆栈、数字、树、字符串、图等算法知识，详细讲解了技术面试的要点，更介绍了系统架构设计题的思考方向。对于每一道题目，本书结合视频，分析了解题思路和面试思路，更有面试技巧分享及面试实战介绍。

本书的目的是让求职者用更短的时间做更充足的准备，并在面试中充分展示自己的特点，高效制胜程序员面试。本书可供IT领域的求职者和在职人员学习参考。

技术面试，是每个心怀梦想的程序员进入理想公司就职，开启事业绚丽篇章的必由之路。越是实力雄厚、待遇上乘、机会无限的公司，对于技术面试也就越重视。不可避免地，进入这些公司的竞争也就越激烈，技术面试的难度也越高，挑战也越大。

经过多年的经验积累，技术面试早已不再局限于考察程序员的编码能力。对于高度复杂而又需要灵活多变的互联网软件产品和服务而言，合格的程序员需要具备全面的能力，包括对原始问题的理解和分析能力、在不同的系统层级中完成设计抽象和资源整合的能力、在多个平行方案中根据具体场景进行取舍和时空置换的能力，更要在团队成员水平并不整齐划一、对项目的理解也存在方向和深度的差异的前提下，组织和规划研发的日常推进，至少能够找准自己的定位并坚实地做好岗位上的输出，并能够对上下游提供必要的支持。这一切的一切，都要在面试时的数小时甚至几十分钟的时间窗口中，通过有限的表达方式展现出来，这并不容易。

LeetCode（力扣）起源于美国硅谷，是最早的在线评测（Online Judge，OJ）平台之一。近年来，中国在全球技术发展中已经逐步成长为主导力量，涌现了大量人类历史上从未有过的领军技术企业，吸引着全球的人才加入。因为预见了这一历史潮流中的潜在需求，我们将力扣引入中国并成立了“力扣中国”，致力于程序员的职业化成长与进步。其中，助力程序员高效地通过技术面试，进入理想的企业，并在真实服务于亿万人的项目中不断深造，是力扣使命的重要组成部分。

我们很高兴地看到，全球的程序员们对于力扣的服务表现出了极大的热情。我们更开心地看到这本书的出版，它的作者吴江很深入地理解了力扣的产品和服务背后的精神：力扣决不是一个简单地供程序员准备面试的“刷题”网站，而是鼓励程序员透过一道道具象的面试题，思考题目背后的计算机体系设计、算法与数据结构、技术和工程取舍、程序设计语法和语义精髓等知识，收获能够为每位程序员职场带来长期助力的“底层能力”。然后在面试现场，通过代码本身，以及代码以外的表达，向面试官尽可能充分地将你已经掌握的知识和能力完整地、忠实地表现出来，并能够让面试官了解到在未来共事的日子里，你还会有更大的发展潜力，成为团队里一股积极的势能。是的，底层能力是一切的基础，是程序员进步和成长的关键，也是力扣一直秉持的信念。所以，这本书的例题全部精选自力扣，也就顺理成章了。

我们了解到作者吴江后续会开通自己的频道，为大家在更大的广度和深度上传播技术面试相关的内容。在此，我们提前预祝他成功。我们希望广大程序员能够通过阅读本书和后续专栏切实受益，更希望大家能够以本书为起点，在力扣上通过更多的学习和练习来有针对性地提升自己的薄弱环节，在专业和事业的道路上不断进步和成长。

力扣
2021年4月

你会打开这本书，一定是被“高效”这个词吸引过来的。作为一名程序员，参加面试最重要的准备工作就是“刷题”，要将大量的时间花在练习算法题上。随着在线练习的题库越来越多，面试者为面试准备的时间也越来越长，而带来的结果则是面试官也需要不断地翻新自己的题库，以防止面试者提前准备了自己选的面试题。

这样一来，面试者和面试官都需要花费大量时间准备面试。而面试者花费了时间和精力准备算法题以后，发现很多题在面试时都没有遇到，在实际工作中对自己也没有帮助。因此帮助面试者在节约准备时间的同时提高业务能力就成为我写这本书的初衷。

我在2018年也因为需要换工作，投递了很多简历，参加了各种企业的面试。花费了大量时间准备却没有在面试中派上用场的挫败感，我深有体会。但是在不断地练习以后，我逐渐有了信心来应对各种算法面试，最终也找到了满意的工作。我想把这段经历中自己结合LeetCode系统地准备面试的经验总结出来，分享给准备面试的各位程序员，包括我自己，让大家在今后的面试准备中少走弯路，于是就有了这本书。

本书的“高效”体现在两个方面。

1.精选适用广泛的算法。既然面试的目的是考核面试者的能力，面试就应该尽量还原工作场景。而只需要用一些常见的算法就可以解决大部分问题，如果最后的算法效率不够高，那么通过白板或实机操作，面试者仍然有机会改进自己的算法。

2.选择最容易写出的代码。程序员喜欢自嘲自己的代码是从GitHub或者Stack Overflow这两个著名的网站上借鉴来的。平时的代码可以引用别人的，面试的时候就应该以快速给出一个正确的实现为目标。

我在准备面试的时候发现，我做一道算法题往往需要半天的时间，这并不是因为我做得慢，而是因为解题过程包括以下步骤。

1.尝试用已有的知识来实现，即使用效率最低的方式也要实现出来。

2.根据LeetCode给出的运行时间和性能测试尝试优化算法。

3.查找相关的资料，比如LeetCode的讨论或相关的理论知识，加深自己的理解。

这些步骤和工作中实现项目功能的步骤一样，首先给出一个正确的方案，然后再进行优化。日常工作中我们可以使用Benchmark或Profiling等工具优化，面试的时候则需要在纸上通过抽象分析来进行优化。

本书的每个问题都会按照这个结构组织，同时也希望读者能按照同样的方式练习算法题，把准备面试的时间花费在更有意义的事情上。

和其他算法书相比，本书显得很“薄”，因为本书专注于“面试”中用到的算法。对于有一定工作经验的面试者来说，面试时很少需要实现排序算法等基础算法，一方面因为它并不是日常的工作内容，另一方面很多语言默认的排序功能需要很长时间的演化才能达到高效和稳定，让面试者在非常短的面试时间内就写出同等质量的代码显然不够合理。如果不凑巧，面试者需要在面试中实现排序算法，那么经过本书的“实现—优化”的练习，面试者仍然可以在面试中写出合格的代码。练习算法题已经成为程序员求职面试准备中非常分散精力但又不得不做的事情，更重要的优化简历、练习自我介绍和总结项目经验等反而没有得到重视，而这些才是让面试官在短时间内了解自己的有效途径。

如何使用本书代码

本书代码使用的编程语言是Python3，在LeetCode提交时需要在语言下拉列表中选择“Python3”，如图0-1所示。

考虑到编程规范的需要，书中的代码和LeetCode的函数名并不一致，读者提交时需要在默认代码中调用书中的函数，如return two_sum（nums,target），如图0-2所示。如果想在LeetCode中模拟白板面试，请读者不要直接复制、粘贴代码，而应该手动敲入代码，这样才能更好地知道自己解题时容易遗漏哪些方面。请记住：我们的目的并不是完成一道题目，而是完全理解该类问题的解题思路。

视频导向图书使用指南

1.什么是视频导向图书？

视频导向图书是一种创新的内容分发形式，它以我们熟悉的图书为载体，但图书只是一个起点。通过视频导向图书，读者可以很容易地使用手边的智能设备，如手机和平板电脑，从图书出发，和图书背后的创作者建立联系，获取视频、直播甚至线下活动等丰富形式的内容，提升获取信息的效率和体验。

2.在视频导向图书上找到入口

所有视频导向图书上都有两种形式的入口。

（1）二维码

二维码是大家非常熟悉、几乎天天都接触的。本书中的二维码入口如图0-3所示（它真的可以扫描）。

为了保证二维码不会失效，我们采用了活码进行跳转。关注微信公众号“内容市场”，使用微信“扫一扫”来扫描书上的二维码，根据页面提示进入微信小程序即可观看讲解视频。也可以使用卷积传媒研发的App——内容市场，来扫描二维码并观看讲解视频。

（2）增强现实触发图

虽然扫描二维码是一种很熟悉的体验，但不得不承认有点太常见，不够酷炫。为此，我们提供了另一种更炫的入口：把一张图直接变成一段视频并就地播放！方法是使用“内容市场”App来扫描触发图，它在本书中如图0-4所示（它真的可以扫描），它位于几乎每一节的开头。

您可以在智能手机上的应用市场等渠道下载和安装“内容市场”App。

单击“内容市场”底部的扫描按钮来扫描触发图，首次识别可能需要等待数秒，但马上您就可以获得相当惊喜的就地播放体验了，而且还可以看到运动跟踪的效果。当然，您不需要一直手持设备并对准触发图，而是随时可以单击“全屏播放”，将视频切换到全屏播放。

3.免费享用增值内容的权益

“内容市场”为读者提供的内容分为两个部分，一是与图书配套的、在图书上提供入口的增值内容，二是由图书的作者再度创作的、并不在图书上提供入口的订阅内容。

本书的读者都可以免费享用所有的增值内容。如果您看了视频感觉有所收获，也可以将它们分享给好友。

订阅内容也有很多免费的，但有些内容可能需要另外付费购买，这完全取决于您的需求和意愿。

4.联系客服

如果读者朋友们在使用软件时遇到了技术故障等问题，可扫描以下二维码咨询客服人员。

卷积传媒

在一些社交网站上可以发现，很多人并不知道如何准备面试，而且在面试的前一天晚上会开始紧张，面试的时候也不知道如何表现。

很多人恐惧面试其实是因为很多问题是平时自己不敢面对的，但是在面试的时候不得不回答，比如自己的特长、自己的职业发展规划等。面试中并不存在“逃避可耻但有用”的说辞，面试官期待的是面试者对这些问题的确切回答。

很多面试者明明自己有实力，但是在面试中却没有发挥好。需要注意的是，面试并不是考试，面试的题目并不存在标准答案，如果没有发挥好，说明准备的策略有问题。参加面试最重要的是让面试官在很短的时间内了解自己，为了达到这个目的，我们就需要在准备的时候提前考虑各种情况，从而可以在面试中尽可能地展示自己的各个方面。

1.1　我是最棒的！

时刻保持自信

“我是最棒的！”这句话在成长励志类文章中比较常见，常见到会引起读者反感的程度，但是很多面试者最缺乏的往往就是自信。

在准备面试的时候，请时刻记住自己是最棒的，并且要在简历中通过项目经历体现出来。

在面试过程中也要保持自信，很多面试官会有意无意地隐藏自己的情绪，不会给出及时的反馈。这个时候面试者需要给自己打气，保持稳定的心态。

在面试结束后，即使没有被录用，也要记住自己是最棒的，只是当前的工作职位并不适合自己。多次被拒绝后，面试者的情绪会逐渐低落，这个时候更需要保持自信心，以迎接下一场面试。

准备简历

在简历中通常要描述自己的工作经历和项目经历，这个时候就应该回想一下，自己在某一项目中发挥了哪些作用，展现了哪方面的特长。

在回顾工作经历的时候也应该回想一下自己当时的感受，感受其实蕴含着很多方面：自己当时的期望，对自己在这段经历中担任的角色是否满意，自己对当时的搭档是否满意。根据感受我们可以梳理出自己对于未来的发展规划，自己喜欢什么样的工作环境，愿意接受哪方面的挑战等。

不要盲目地投递简历，没有做功课就参加面试，会让面试官对我们的第一印象大打折扣。了解职位也是面试准备的一部分，公司的企业文化、所处行业还有工作氛围都和面试者息息相关。设想一下，如果面试者不喜欢大公司冗长烦琐的工作流程，可以预见即使面试通过，没多久也会重新换工作，这样对自己和企业来说都是不负责任的。

准备简历的时候请牢记自己是最棒的，更需要让查看简历的人知道自己棒在哪里，从而可以顺利地进入下一步的面试。

面试是一场销售

面试和销售有一些相似之处，都需要让对方在短时间内了解并买下自己推销的“商品”，面试时的“商品”就是面试者自己。就像商品需要包装一样，面试者在面试中展现出良好的精神状态会为自己加分。

而如何介绍自己就类似销售中的话术，不同的职位对于面试者的要求不一样，在面试前准备的时候需要再次熟读职位要求，针对职位要求调整自我介绍的重点。比如，有些职位看重创造性，有些职位则看重严谨性。准备的时候就需要仔细回想自己的工作经历，找出一些实例证明自己确实有相应的特点。

另外，面试官也需要展示企业的优点以吸引优秀的面试者，面试者则需要多问问题，全面了解企业和职位，避免出现到了新岗位后不适应而很快就萌生退意的情况。

1.2　常见问题的准备

有一些必须准备的常见面试问题，在准备时应考虑清楚这些问题实际考查的内容，下面是一些例子。

请介绍一下你自己

这个问题一般是面试的开场，如果应聘外企，还需要做好使用外语回答的准备。面试者在这个环节常见的错误是仅复述一遍自己的简历，并没有意识到需要解答面试的根本性问题，即“我为什么要雇用你？”

回答这个问题，就要强调自己为什么能胜任应聘的职位，以及自己未来的发展和职位的契合度。比如，“我在某某行业有X年的工作经验，我对于用户体验的优化很有兴趣，平时会和产品经理讨论一些想法”，这样的一个开场白就讲明了自己的长处，并暗示了自己未来的发展方向（用户体验的优化）。接下来面试官就可以验证面试者的特长是否属实，以及向面试者介绍当前的职位是否符合她/他想要的发展方向。

这个问题对于全球的面试者来说都是一个困扰，因为很少有人认为自己能回答得很好。虽然面试官在这个时候不太会给出反馈，但是如果在这个环节能够让面试官满意，后面的环节他可能倾向帮助面试者更好地展现自己，避免面试者被题目困住。

准备这个问题需要掌握以下几个要点。

1.“我是谁”。使用简短的语言介绍自己的长处，给面试官留下印象。

2.“我的专业背景”。用一句话总结自己的行业背景，如果是跨行业面试，可能还需要突出工作内容的契合度。

3.“我为什么想应聘这个职位”。一方面体现自己了解应聘的职位，另一方面也要体现出自己的职业规划与该职位是符合的，愿意在该职位长期工作。

请讲述工作中最难忘的经历

这个问题隐含了基于行为的面试。面试者需要回答出一段工作经历，并讲述自己在这段工作经历中发挥的作用。

回答问题前可以询问面试官给的时间长短，根据时间准备不同的讲述重点。如果时间充分可以讲述一下自己当时对项目的期望，以及自己是如何努力让项目在符合期望的方向上推进的。

你最大的缺点是什么

问这个问题的面试官一般被认为是“阴险”的，因为面试者不可能真的把自己最大的缺点讲出来，比如懒、没有耐心等，也不能虚伪地回答“我最大的缺点就是没有缺点”。

如果不想回答，不妨直白地告诉面试官，自己在平时的工作中人际关系还不错，所以并不了解自己到底有哪些缺点为他人造成了困扰。如果想回答出彩的话，面试者需要明白面试官想了解的是面试者自己不容易让别人接受的部分，相应的可以加一些正面的解释。比如懒是程序员常见的缺点，可以解释一下自己是因为不喜欢重复才让别人觉得自己懒。

1.3　技术相关面试题的准备

对于程序员来说，算法、数据结构和系统设计方面的问题在面试中常常会遇到，而且这些题目在面试中的比重越来越大，面试不再仅仅是针对简历的提问。很多面试者非常担心因为做不出这些题目而被淘汰，因此花费了很多时间来准备。

需要注意的是，在准备这些题目的时候，最好从应聘的职位和自己平时的工作出发，不要花太多时间。面试官出题的目的并不是为难面试者，而是考查面试者能否胜任该职位。不可否认，一些大公司喜欢使用难题来筛选面试者，但是面试并不是考试，并不能保证做出了所有的难题就能得到该职位。

本书从第03章开始会介绍一些关键的算法题和系统设计题，并给出容易理解的解法，目的是让面试者不会被常见题目卡住，即使遇到不会的题目也能从平时练习的题目中获得灵感，至少给出一个次优解。

除了本书的题目外，还建议大家使用一些网站和书籍辅助练习。

LeetCode

LeetCode是推荐最多的算法题练习网站，本书的算法题也都精选自LeetCode。我认为LeetCode有以下几个优点。

1.测试覆盖率高。在提交代码以后，LeetCode会跑很多测试来验证代码的正确性，而且很多题目的测试对于极端边界情况、复杂度和性能的要求都有全面的考虑。为了保证代码的正确性，做题目的时候要养成审题的习惯，仔细分析题目的条件范围，不要因为极端案例导致程序失败。

2.支持的语言比较多和新。LeetCode会定期更新支持的语言的版本，保证能够利用到最新的语言特性。

3.讨论内容丰富。Leet Code现在有中文和英文两个版本，每个版本下的评论都很丰富，通过阅读他人的评论可以加深我们对题目的理解，获得新的思路。

当然，LeetCode也有一些缺点，比如题目数量太多、不够精练，而与字符串相关的练习题偏少等。

《算法》第四版

这本由Robert Sedgewick和Kevin Wayne编写的算法书系统地介绍了各种常见的算法。我推荐它的原因是随着互联网的流行，与字符串相关的算法越来越重要，而这本书就专门把字符串列出讲解。

在硬件更新日新月异的情况下，很多因为硬件资源不足而发明出来的经典算法变得越来越不重要。在准备面试的时候应该把更多的精力留给和工作相关的算法，而不是只有面试时才会用到的算法，比如翻转二叉树。

High Scalability

这个网站会更新一些常见网站的系统设计，对于平时除了工作外很难接触到其他系统的程序员来说，它是一个了解不同系统如何设计的很好的网站。推荐面试者在面试前结合自己的分析和网站的结论做一些系统设计的练习。

《程序员面试金典》

这本书是由CareerCup创始人编写的，也是本书的灵感来源之一。这本书有更详细的面试场景的分析，以及更多的面试题的讲解。推荐阅读该书的第01~08章，这是该书的亮点部分。

1.4　“你是最棒的”

本书的目标是让读者在面试中能够得到面试官的认同，最终目标是让面试官不由地赞叹，“你是最棒的"。希望读者在本书的帮助下，能够高效地准备面试，从而在面试中充分地展现自己。

大多数人即使参加了很多面试，仍然没有认清面试的本质。这一章我们就来探讨一下面试到底是什么，从而帮助读者以更好的心态准备面试和接受面试的结果。

2.1　“面试”一词的含义

“面谈”多于“面试”

“面试”的英文是Interview，其本意是面对面谈话，引申为采访、面试等。和“面试”相比，“面谈”是更贴切的说法。

理想的面试场景应该是，面试者和面试官轻松地交流，互相了解。如果面试者紧张，面试官也会帮助他/她克服这种紧张情绪，从而展现出最好的一面。

面试和考试的不同

面试并不是考试，相信很多读者从小到大经历了大大小小的许多考试，对考试非常了解。但是面试并不是考试，虽然面试和考试同样都是考查能力，但是面试仍然有很多不同于考试的地方。

1.面试没有标准答案。虽然部分算法题有最佳答案，但是对于面试者来说，并不是给出最佳答案就能像考试拿到高分一样被录取。和最终答案相比，面试官更想考查的是面试者的交流沟通能力和思考过程。在日常工作中，我们将更多的时间花在了探讨需求和接口规范上，所以如果沟通顺利可以达到事半功倍的效果。

2.面试双方是平等的。虽然很多情况下面试官占据面试的主导地位，但是这并不意味着面试官的身份就高些。面试的首要目的是面试双方平等交流，加深对于对方的了解，而不是在面试中争强好胜，证明自己比对方更厉害。

3.面试是双向选择。虽然大多数情况下是面试官挑选面试者，但是面试者也应该坚持自己挑选公司的标准。如果面试者有效地准备面试，积极地投递简历，同时拿到多个录用通知，这样可以在更有利的条件下挑选公司。

了解面试职位

前一章给出了面试者如何准备，以让面试官更好地了解自己的建议，这里再介绍面试者在面试前应该如何了解应聘的职位，毕竟花费了很多精力但最后选择了一个不合适的职位，对面试者来说也是很麻烦的一件事情。

不合适的职位有以下特点，希望面试者在面试前和面试中能够对相关方面进行了解。

1.发挥不出特长。比如面试者擅长处理数据库设计，但是由于公司中有专职的数据库设计人员，或者由于业务的特性，新的职位并不能让面试者继续发挥这方面的特长。此外，由于业务调整，面试者也可能面临工作内容更换，需放弃自己特长的情况。这时就要看面试者自己的职业规划。计算机行业的特点就是变化很快，比如随着互联网的发展，为了满足更大的用户量，很多业务会选择非关系型数据库而不是关系型数据库。技术毕竟是为业务服务的，希望面试者在总结自己擅长哪些技术的同时，多花一些时间总结一下自己擅长解决哪方面的问题，向着“解决方案”专家的方向发展。

2.职业发展不顺利。一方面，很多新职位在不断地被创造出来，但是没过几年热度就会消退，出现供大于求的情况；另一方面，随着技术更新换代，很多旧的职位也在消失。我们在编程的时候提倡“拥抱变化”，在面对行业变化时也应该保持同样的态度。同时公司和所在行业的发展情况也会影响员工的职业发展前景。

3.不适应办公室关系。很多时候我们会发现，面试双方留下的第一印象是非常准确的。面试的一个重要作用就是让面试者提前和未来可能的同事们进行沟通，如果面试的时候沟通不顺畅，很可能意味着未来工作中也需要很长的磨合期，对公司和面试者都不好。面试者在面试中除了和面试官进行相互了解外，还应该了解公司的文化和工作流程，对自己在意的公司文化都应该及时地了解。

现实中并不存在完美的职位，但是提前了解职位的信息有助于面试者做出更好的选择。同时公司除了看重面试者的能力外，也会衡量面试者和职位的匹配度，所以被心仪的公司拒绝时不需要伤心，而是接受职位不适合的情况。

小结

面试是一个相互了解的过程，面试者应该在准备过程中积极地了解目标职位和所在行业，帮助自己做出更好的判断。

2.2　一次失败的面试

这个失败的面试故事不是发生在我身上的，虽然我也有很多可以分享的面试故事，但是并没有这个故事典型，希望可以引起读者更多的思考。

Homebrew作者面试失败的经过

Homebrew是Mac OS上使用最广泛的包管理软件。Mac OS并没有官方的软件管理系统，用户安装软件需要自行下载或编译，Homebrew的出现让这个过程变得简单。因为扩展性好，所以Homebrew很快就收到了社区贡献的大量常用软件，在Mac OS上大多数软件通过Homebrew就可以直接安装。从这个方面来看，Homebrew的作者Max Howell的系统设计能力非常强，即使是业界知名公司也会抢着要他。

Howell同时也是Twitter移动客户端TweetDeck的首席开发者，然而他在面试谷歌的时候非常不愉快。他把这次经历记录在了Twitter上。

在这则动态中，Howell抱怨说，虽然90%的谷歌工程师都用他写的软件（Homebrew），但是因为他没法在白板上翻转二叉树，所以面试失败了。他在回复中进一步提到，虽然面试的是iOS开发职位，但是整个面试过程一点都没有问到相关的问题。

这件事引起了广泛的讨论，一方面是因为Homebrew的知名度，另一方面则是因为面试的不合理性已经是普遍现象，很多人也借此分享自己在面试中遇到的不合理要求。同时大家也很惋惜，谷歌作为业界数一数二的大公司，在招聘的时候却仍然是原始和粗糙的，不懂得变通。

白板面试

除了当事双方的知名度引起了热烈讨论外，这件事的最大焦点是面试的手段——白板面试。白板面试指的是让程序员站在白板前，完成指定的编码过程，实现面试官提出的要求。在远程面试中，面试官也会使用在线文档等工具强迫程序员使用不熟悉的工具编程，从而达到白板面试的效果。

我反对白板面试，理由是它并不能真正考查面试者的能力。面试者平时并不在白板或在线文档上工作，需要借助熟悉的编辑器或集成开发环境提供语法突显（又称语法高亮）、代码完成和代码跳转等功能，从而能专心地实现功能。

但是白板面试仍然有很多人推崇，他们相信在没有任何辅助手段的情况下，才能体现程序员的真实水平。虽然我们强调企业更倾向招聘合适的人而不是能力强的人，但是显然企业不认为白板面试是不适合的手段。

在当前白板面试占主流的情况下，程序员不可避免地会遇到白板面试。我的建议是把这个过程当作平时探讨代码功能的过程，别忘了面试是你和面试官双人或多人完成的。如果面试官过于强调白板面试的代码正确性，我们只能为这些公司表示遗憾，他们在用错误的方式挑选程序员，因此面试失败的程序员只是运气不好。

本书在介绍算法题的时候会给出一些白板面试的对策，其实这些对策也适合使用工具的编程面试。针对不同的难题，本书会总结出面试者在审题时需要注意的点，需要和面试官探讨的细节，以及如何说明解题思路。做好以上步骤后，只要面试者平时的代码风格优秀，相信白板面试就不会成为障碍。

运气在面试中的重要性

这一面试故事说明，面试中运气占非常大的成分。大家都喜欢大公司，但是大公司有很多不同的项目组，每个项目组有自己不同的文化，每个面试官的风格也不同。如果面试时遇到了不适合的项目组或面试官，那就只能等待下次机会了。

其实Howell面试的组是非常适合他的，因为Howell本身做的就是iOS软件的开发，而他面试的组也正好是iOS项目组。Howell只是不幸遇上了不懂变通的面试官，即使Howell面试成功，未来他可能也需要和这位面试官有较长的磨合过程，从这一点来说这个面试失败的最大原因就是双方不合适。

翻转二叉树是个不常见的算法，在处理实际问题时很少需要用到。虽然很多人觉得这一道题很基础，但是我不认为在面试中考查平时不使用的算法是一个好主意，而且这道题除了考查递归以外并没有太多价值。

消除运气影响

如果是一位合格的面试官，在面试者答不出某道算法题的时候，为了消除偶然因素的影响，就应该出一道不同领域的算法题考查面试者的基础，而不是像这个故事中一样直接拒绝面试者。

而面试者在准备面试的时候，建议尽量练习通用的算法，达到举一反三的目的。本书挑选的算法题都是以通用为主，希望读者能真正明白某一道题目，并仔细分析其中的难点，这样再遇到类似的题目时就不会紧张了。本书会使用图形和表格帮助读者分析问题，如果面试者在面试中也能使用同样的方法，就会让面试官更容易理解自己的思路，从而顺利地通过算法题的考验。

小结

Howell最后去了苹果公司，这说明方向对了也会有好的结局，毕竟不讲道理的面试官不是常见的，被拒绝并不能说明面试者能力差。

2.3　关于难题

很多面试者认为在时间不足的情况下，应该优先练习难题。但是常见的编程练习网站，题目难度划分的标准往往是代码运行使用的时间，而不是按照问题的复杂度。还有一点，难题并不一定通用，比如“缺少的最小的正整数”一题。

问题描述

给定一个未排序的整数数组，请找出其中没有出现的最小的正整数。

示例

提示

不考虑空间复杂度？

不考虑空间复杂度的话，这道题的难度瞬间变得简单了。首先构造一个和输入等长的数组；然后每次遍历输入的数组，把对应下标的值设为True；最后返回第一个False对应的下标，如代码2-1所示。

代码2-1：不考虑空间复杂度，解决缺少的第一个正数问题

def fi rstMissingPositive(nums: List[int]) -> int:
    l = len(nums)
    x = [False]*(l+1)
    # 遍历给定数组，在新构造的数组中相同的下标填入True
    for i in nums:
        if i > 0 and i <= l:
            x[i] = True
    # 检查新构造的数组，返回第一个值为False的下标
    for i in range(1, l+1):
        if not x[i]:
            return i
    # 如果遍历正常结束，返回数组的长度加1
    return l+1

空间复杂度为常数？

原题关于空间复杂度为常数的要求，其实在工作中是一个不合理的要求，现在（2020年），16GB的服务器内存只要500元就能买到，1 TB内存只需要32000元左右，这对于企业来说并不是很高的成本。和早期嵌入式系统必须对内存精打细算不同，现在的系统只要不造成内存泄露，多用一些内存并不是太大的问题。

某些算法为了追求节省内存，需要反复对内存进行读写，这其实反而造成了速度的下降。虽然读写内存和CPU计算的时间看上去一样，但是现代CPU的速度已经远远超过了内存速度。在2015年出版的《性能之巅：洞悉系统、企业与云计算》一书中，作者比较了CPU和内存的速度，如表2-1所示。CPU的速度已经远远超过内存，内存做一次读写的同时CPU可以执行几百条指令，为了节省内存而频繁读写内存只会让程序的性能下降。

现代CPU为了快速读写数据，还提供了L1、L2和L3三层缓存，为了充分利用三层缓存加快执行速度，程序的数据应该多利用连续的内存。这意味着程序应该多使用数组和哈希表等数据结构，而不是链表和树等内存不连续的数据结构。

编程的首要任务是完成功能，而不是一味地节约内存。如果因为一味地节约内存或追求高性能计算而忽略了编码的规范性，那么不只会造成未来维护代码更困难，也会使得后续利用一些优化手段（如GPU加速）变得困难。

本章总结

本章梳理了面试的本质，并分析了著名程序员面试失败的故事，希望读者能够以平常心看待面试，更有针对性地准备面试。