Question

面试官在通过简历及行为面试大致了解应聘者的背景之后，接下来就要开始技术面试了。一轮1小时的面试，通常技术面试会占据40～50分钟。这是面试的重头戏，对面试的结果起决定性作用。虽然不同公司里不同面试官的背景、性格各不相同，但总体来说他们都会关注应聘者5种素质：扎实的基础知识、能写高质量的代码、分析问题时思路清晰、能优化时间效率和空间效率，以及学习沟通等各方面的能力（如图1.4所示）。

图1.4　应聘者需要具备的素质

应聘者在面试之前需要做足准备，对编程语言、数据结构和算法等基础知识有全面的了解。面试的时候如果遇到简单的问题，应聘者一定要注重细节，写出完整、鲁棒的代码。如果遇到复杂的问题，应聘者可以通过画图、举具体例子分析和分解复杂问题等方法先理清思路再动手编程。除此之外，应聘者还应该不断优化时间效率和空间效率，力求找到最优的解法。在面试过程中，应聘者还应该主动提问，以弄清楚题目的要求，表现自己的沟通能力。当面试官前后问的两个问题有相关性的时候，尽量把解决前面问题的思路迁移到后面的问题中去，展示自己良好的学习能力。如果能做到这么几点，那么通过面试获得心仪的职位将是水到渠成的事情。

1．扎实的基础知识

扎实的基本功是成为优秀程序员的前提条件，因此面试官首要关注的应聘者素质就是是否具备扎实的基础知识。通常基本功在编程面试环节体现在3个方面：编程语言、数据结构和算法。

首先，每个程序员至少要掌握一两门编程语言。面试官从应聘者在面试过程中写的代码及跟进的提问中，能看出其编程语言掌握的熟练程度。以大部分公司面试要求的C++举例。如果写的函数需要传入一个指针，面试官可能会问是否需要为该指针加上const，把const加在指针不同的位置是否有区别；如果写的函数需要传入的参数是一个复杂类型的实例，面试官可能会问传入值参数和传入引用参数有什么区别，什么时候需要为传入的引用参数加上const。

其次，数据结构通常是编程面试过程中考查的重点。在参加面试之前，应聘者需要熟练掌握链表、树、栈、队列和哈希表等数据结构，以及它们的操作。如果我们留意各大公司的面试题，就会发现链表和二叉树相关的问题是很多面试官喜欢问的问题。这方面的问题看似比较简单，但要真正掌握也不容易，特别适合在这么短的面试时间内检验应聘者的基本功。如果应聘者事先对链表的插入和删除结点了如指掌，对二叉树的各种遍历方法的循环和递归写法都烂熟于胸，那么真正到了面试的时候也就游刃有余了。

最后，大部分公司都会注重考查查找、排序等算法。应聘者可以在了解各种查找和排序算法的基础上，重点掌握二分查找、归并排序和快速排序，因为很多面试题都只是这些算法的变体而已。比如面试题8旋转数组的最小数字和面试题38数字在排序数组中出现的次数的本质是考查二分查找，而面试题36数组中的逆序对实际上是考查归并排序。少数对算法很重视的公司比如谷歌或者百度，还会要求应聘者熟练掌握动态规划和贪婪算法。如果应聘者对动态规划算法很熟悉，那么他就能很轻松地解决面试题31连续子数组的最大和。

在本书的第2章面试需要的基础知识中，我们将详细介绍应聘者需要熟练掌握的基础知识。

2．高质量的代码

只有注重质量的程序员，才能写出鲁棒稳定的大型软件。在面试过程中，面试官总会格外关注边界条件、特殊输入等看似细枝末节但实质至关重要的地方，以考查应聘者是否注重代码质量。很多时候，面试官发现应聘者写出来的代码只能完成最基本的功能，一旦输入特殊的边界条件参数就会错误百出甚至程序崩溃。

总有些应聘者很困惑：面试的时候觉得题目很简单，感觉自己都做出来了，可最后为什么被拒了呢？面试被拒有很多种可能，比如面试官认为你性格不适合、态度不够诚恳等。但在技术面试过程中，这些都不是最重要的。技术面试的面试官一般都是程序员，程序员通常没有那么多想法，他们只认一个理：题目做对、做完整了，就让你通过面试；否则失败。所以遇到简单题目却被拒的情况，应聘者应认真反思在思路或者代码中存在哪些漏洞。

以微软面试开发工程师时最常用的一个问题为例：把一个字符串转换成整数。这个题目很简单，很多人都能在三分钟之内写出如下不到10行的代码：

看了上面的代码，你是不是觉得微软面试很容易？如果你真的这么想，那你可能又要被拒了。

通常越是简单的问题，面试官的期望值就会越高。如果题目很简单，面试官就会期待应聘者能够很完整地解决问题，除了完成基本功能之外，还要考虑到边界条件、错误处理等各个方面。比如这道题，面试官不仅仅是期待你能完成把字符串转换成整数这个最起码的要求，而且希望你能考虑到各种特殊的输入。面试官至少会期待应聘者能够在不需要提示的情况下，考虑到输入的字符串中有非数字字符和正负号，要考虑到最大的正整数和最小的负整数以及溢出。同时面试官还期待应聘者能够考虑到当输入的字符串不能转换成整数时，应该如何做错误处理。当把这个问题的方方面面都考虑到的时候，我们就不会再认为这道题简单了。

除了问题考虑不全面之外，还有一个面试官不能容忍的错误就是程序不够鲁棒。以前面的那段代码为例，只要输入一个空指针，程序立即崩溃。这样的代码如果加入到软件当中，将是灾难。因此当面试官看到代码中对空指针没有判断并加以特殊处理的时候，通常他连往下看的兴趣都没有。

当然，不是所有与鲁棒性相关的问题都和前面的代码那样明显。再举一个很多人都曾经被面试过的问题：求链表中的倒数第k个结点。有不少人在面试之前在网上看过这个题目，因此知道思路是用两个指针，第一个指针先走k－1步，然后两个指针一起走。当第一个指针走到尾结点的时候，第二个指针指向的就是倒数第k个结点。于是他大笔一挥，写下了下面的代码：

写完之后，应聘者看到自己已经判断了输入的指针是不是空指针并做了特殊处理，于是以为这次面试必定能顺利通过，可是他没有想到的是这段代码中仍然有很严重的问题：当链表中的结点总数小于k的时候，程序还是会崩溃。另外，当输入的k为0时，同样也会引起程序崩溃。因此，几天之后他收到的仍然不是Offer而是拒信。

要想很好地解决前面的问题，最好的办法是在动手写代码之后想好测试用例。只有把各种可能的输入事先都想好了，才能在写代码的时候把各种情况都做相应的处理。写完代码之后，也不要立刻给面试官检查，而是先在心里默默地运行。当输入之前想好的所有测试用例都能得到合理的输出时，再把代码交给面试官。做到了这一步，通过面试拿到Offer就是顺理成章的事情了。

在本书的第3章高质量的代码中，我们将详细讨论提高代码质量的方法。

面试小提示：

面试官除了希望应聘者的代码能够完成基本的功能之外，还会关注应聘者是否考虑了边界条件、特殊输入（比如NULL指针，空字符串等）及错误处理。

3．清晰的思路

只有思路清晰，应聘者才有可能在面试过程中解决复杂的问题。有些时候面试官会有意出一些比较复杂的问题，以考查应聘者能否在短时间内形成清晰的思路并解决问题。对于确实很复杂的问题，面试官甚至不期待应聘者能在面试不到一个小时的时间里给出完整的答案，他更看重的可能还是应聘者是否有清晰的思路。面试官通常不喜欢应聘者在没有形成清晰思路之前就草率地开始写代码，这样写出来的代码容易逻辑混乱、错误百出。

应聘者可以用几个简单的方法帮助自己形成清晰的思路。首先是举几个简单的具体例子让自己理解问题。当我们一眼看不出问题中隐藏的规律的时候，可以试着用一两个具体的例子模拟操作的过程，这样说不定就能通过具体的例子找到抽象的规律。其次可以试着用图形表示抽象的数据结构。像分析与链表、二叉树相关的题目，我们都可以画出它们的结构来简化题目。最后可以试着把复杂的问题分解成若干个简单的子问题，再一一解决。很多基于递归的思路，包括分治法和动态规划，都是把复杂的问题分解成一个或者多个简单的子问题。

比如把二叉搜索树转换成排序的双向链表这个问题就很复杂。遇到这个问题，我们不妨先画出一两个具体的二叉搜索树，直观地感受二叉搜索树和排序的双向链表有哪些联系。如果一下子找不出转换的规律，我们可以把整个二叉树看成3个部分：根结点、左子树和右子树。当我们递归地把转换左右子树这两个子问题解决之后，再把转换左右子树得到的链表和根结点链接起来，整个问题也就解决了（详见面试题27二叉搜索树与双向链表）。

在本书的第4章解决面试题的思路中，我们将详细讨论遇到复杂问题时如何采用画图、举例和分解问题等方法帮助我们解决问题。

面试小提示：

如果在面试的时候遇到难题，我们有3种办法分析、解决复杂的问题：画图能使抽象问题形象化，举例使抽象问题具体化，分解使复杂问题简单化。

4．优化效率的能力

优秀的程序员对时间和内存的消耗锱铢必较，他们很有激情地不断优化自己的代码。当面试官出的题目有多种解法的时候，通常他会期待应聘者最终能够找到最优解。当面试官提示还有更好的解法的时候，应聘者不能放弃思考，而应该努力寻找在时间消耗或者空间消耗上可以优化的地方。

要想优化时间或者空间效率，首先要知道如何分析效率。即使是同一个算法，用不同方法实现的效率可能也会大不相同，我们要能够分析出算法及其代码实现的效率。例如求斐波那契数列，很多人喜欢用递归公式f（n）=f（n－1）＋f（n－2）求解。如果分析它的递归调用树，我们就会发现有大量的计算是重复的，时间复杂度以n的指数增加。但如果我们先求f（1）、f（2），再根据f（1）和f（2）求出f（3），接下来根据f（2）、f（3）求出f（4），并以此类推用一个循环求出f（n），这种计算方法的时间效率就只有O（n），比前面递归的方法要好得多。

要想优化代码的效率，我们还要熟知各种数据结构的优缺点，并能选择合适的数据结构解决问题。我们在数组中根据下标可以用O（1）时间完成查找。数组的这个特征可以用来实现简单的哈希表解决很多问题，比如面试题35第一个只出现一次的字符。为了解决面试题30最小的k个数，我们需要一个数据容器来存储k个数字。在这个数据容器中，我们希望能够快速地找到最大值并且能快速地替换其中的数字。经过权衡，我们发现二叉树比如最大堆或者红黑树都是实现这个数据容器的不错选择。

要想优化代码的效率，我们也要熟练掌握常用的算法。面试中最常用的算法是查找和排序。如果从头到尾顺序扫描一个数组，我们需要O（n）时间才能完成查找操作。但如果数组是排序的，应用二分查找算法就能把时间复杂度降低到O（logn）（如面试题8旋转数组的最小值和面试题38数字在排序数组中出现的次数）。排序算法除了能够给数组排序之外，还能用来解决其他问题。比如快速排序算法中的Partition函数能够用来在n个数里查找第k大的数字，从而解决面试题29数组中出现次数超过一半的数字和面试题30最小的k个数。归并排序算法能够实现在O（nlogn）时间统计n个数字中的逆序对数目（面试题36数组中的逆序对）。

在本书的第5章优化时间空间效率中，我们将详细讨论如何从时间效率和空间效率两方面去做优化。

5．优秀的综合能力

在面试过程中，应聘者除了展示自己的编程能力和技术功底之外，还需要展示自己的软技能（Soft Skills），诸如自己的沟通能力和学习能力。随着软件系统的规模越来越大，软件开发已经告别了单打独斗的年代，程序员与他人的沟通变得越来越重要。在面试过程中，面试官会观察应聘者在介绍项目经验或者算法思路时是否观点明确、逻辑清晰，并以此判断其沟通能力的强弱。另外，面试官也会从应聘者说话的神态和语气来判断他是否有团队合作的意识。通常面试官不会喜欢高傲或者轻视合作者的人。

IT行业知识更新很快，因此程序员只有具备很好的学习能力才能跟上知识更替的步伐。通常面试官有两种办法考查应聘者的学习能力。面试官的第一种方法是询问应聘者最近在看什么书、从中学到了哪些新技术。面试官可以用这个问题了解应聘者的学习愿望和学习能力。面试官的第二种方法是抛出一个新概念，接下来他会观察应聘者能不能在较短时间内理解这个新概念并解决相关的问题。比如面试官要求应聘者计算第1500个丑数。很多人都没有听说过丑数这个概念。这个时候面试官就会观察应聘者面对丑数这个新概念时，能不能经过提问、思考、再提问的过程，最终找出丑数的规律从而找到解决方案（详见面试题34丑数）。

知识迁移能力是一种特殊的学习能力。如果我们能够把已经掌握的知识迁移到其他领域，那么学习新技术或者解决新问题就会变得容易。面试官经常会先问一个简单的问题，再问一个很复杂但和前面的简单问题相关的问题。这个时候面试官期待应聘者能够从简单问题中得到启示，从而找到解决复杂问题的窍门。比如面试官先要求应聘者写一个函数求斐波那契数列，再问一个青蛙跳台阶的问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。请问这只青蛙跳上n级台阶总共有多少种跳法。应聘者如果具有较强的知识迁移能力，就能分析出青蛙跳台阶问题实质上只是斐波那契数列的一个应用（详见面试题9斐波那契数列）。

还有不少面试官喜欢考查应聘者的抽象建模能力和发散思维能力。面试官从日常生活中提炼出问题，比如面试题44扑克牌中的顺子，考查应聘者能不能把问题抽象出来用合理的数据结构表示，并找到其中的规律解决这个问题。面试官也可以限制应聘者不得使用常规方法，这要求应聘者具备创新精神，能够打开思路从多角度去分析、解决问题。比如在面试题47不用加减乘除做加法中，面试官期待应聘者能够打开思路，用位运算实现整数的加法。

我们将在本书的第6章面试中的各项能力中用具体的面试题详细讨论上述能力在面试中的重要作用。