第3章 高质量的代码 3.1 面试官谈代码质量 “一般会考查代码的容错处理能力，对一些特别的输入会询问应聘人员是否考虑、如何处理。不能容忍代码只是针对一种假想的‘正常值’进行处理，不考虑异常状况，也不考虑资源的回收等问题。” ——殷焰（支付宝，高级安全测试工程师） “如果是因为粗心犯错，可以原谅，因为毕竟面试的时候会紧张；不能容忍的是，该掌握的知识点却没有掌握，而且提醒了还不知道。比如下面的：  注：1 由于精度原因不能用等号判断两个小数是否相等，请参考面试题11“数值的整数次方”。 ——马凌洲（Autodesk，Software Development Manager） “最不能容忍功能错误，忽略边界情况。” ——尹彦（Intel，Software Engineer） “如果一个程序员连变量、函数命名都毫无章法，解决一个具体问题都找不到一个最合适的数据结构，这会让面试官印象大打折扣，因为这个只能说明他程序写得太少，不够熟悉。” ——吴斌（NVidia，Graphics Architect） “我会从程序的正确性和鲁棒性两方面检验代码的质量。会关注对输入参数的检查、处理错误和异常的方式、命名方式等。对于没有工作经验的学生，程序正确性之外的错误基本都能容忍，但经过提示后希望能够很快解决。对于有工作经验的人，不能容忍考虑不周到、有明显的鲁棒性错误。” ——田超（微软，SDE II） 3.2 代码的规范性 面试官是根据应聘者写出的代码来决定是否录用他的。如果应聘者代码写得不够规范，影响面试官阅读代码的兴致，那面试官就会默默地减去几分。如图3.1所示，书写、布局和命名都决定着代码的规范性。  图3.1 影响代码规范性的因素：书写、布局和命名 首先，规范的代码书写清晰。绝大部分面试都是要求应聘者在白纸或者白板上书写。由于现代人已经习惯了敲键盘打字，手写变得越来越不习惯，因此写出来的字潦草难辨。虽然应聘者没有必要为了面试特意去练字，但在面试过程中减慢写字的速度，尽量把每个字母写清楚还是很有必要的。不用担心没有时间去写代码，通常编程面试的代码量都不会超过50行，书写不用花多少时间，关键是在写代码之前形成清晰的思路并能把思路用编程语言清楚地书写出来。 其次，规范的代码布局清晰。平时程序员在集成开发环境如Visual Studio里面写代码，依靠专业工具调整代码的布局，加入合理的缩进并让括号对齐成对呈现。离开了这些工具手写代码，我们就要格外注意布局问题。当循环、判断较多，逻辑较复杂时，缩进的层次可能会比较多。如果布局不够清晰，缩进也不能体现代码的逻辑，面试官面对这样的代码将会头晕脑胀。 最后，规范的代码命名合理。很多初学编程的人在写代码时总是习惯用最简单的名字来命名，变量名是i、j、k，函数名是f、g、h。由于这样的名字不能告诉读者对应的变量或者函数的意义，代码一长就会变得晦涩难懂。强烈建议应聘者在写代码的时候，用完整的英文单词组合命名变量和函数，比如函数需要传入一个二叉树的根结点作为参数，则可以把该参数命名为BinaryTreeNode\* pRoot，不要因为这样会多写几个字母而觉得麻烦。如果一眼能看出变量、函数的用途，应聘者就能避免自己搞混淆而犯一些低级的错误。同时合理的命名也能让面试官一眼就能读懂代码的意图，而不是让他去猜变量m到底是数组中的最大值还是最小值。 面试小提示： 应聘者在写代码的时候，最好用完整的英文单词组合命名变量和函数，以便面试官能一眼读懂代码的意图。 3.3 代码的完整性 在面试的过程中，面试官会非常关注应聘者考虑问题是否周全。面试官通过检查代码是否完整来考查应聘者的思维是否全面。通常面试官会检查应聘者的代码是否完成了基本功能、输入边界值是否能得到正确的输出、是否对各种不合规范的非法输入做出了合理的错误处理。 1．从3方面确保代码的完整性 应聘者在写代码之前，首先要把可能的输入都想清楚，从而避免在程序中出现各种各样的质量漏洞。也就是说在编码之前要考虑单元测试。如果能够设计全面的单元测试用例并在代码中体现出来，那么写出的代码自然也就是完整正确的了。通常我们可以从功能测试、边界测试和负面测试三方面设计测试用例，以确保代码的完整性（如图3.2所示）。  图3.2 从功能测试、边界测试、负面测试3个方面设计测试用例，以保证代码的完整性 首先要考虑的是普通功能测试的测试用例。我们首先要保证写出的代码能够完成面试官要求的基本功能。比如面试题要求完成的功能是把字符串转换成整数，我们就可以考虑输入字符串”123”来测试自己写的代码。这里要把零、正数和负数都考虑进去。 考虑功能测试的时候，我们要尽量突破常规思维的限制。面试的时候我们经常受到惯性思维的限制，从而看不到更多的功能需求。比如面试题12“打印1到最大的n位数”，很多人觉得这题很简单。最大的3位数是999、最大的4位数是9999，这些数字很容易就能算出来。但是最大的n位数都能用int型表示吗？超出int的范围我们可以考虑long long类型，超出long long能够表示的范围呢？面试官是不是要求考虑任意大的数字？如果面试官确认题目要求的是任意大的数字，那么这个题目就是一个大数问题，此时我们需要特殊的数据结构来表示数字，比如用字符串或者数组来表示大的数字，以确保不会溢出。 其次需要考虑各种边界值的测试用例。很多时候我们的代码中都会有循环或者递归。如果我们的代码是基于循环，那么结束循环的边界条件是否正确？如果是递归，递归终止的边界值是否正确？这些都是边界测试时要考虑的用例。还是以字符串转换成整数的问题为例，我们写出的代码应该确保能够正确转换最大的正整数和最小的负整数。 最后还需要考虑各种可能的错误的输入，也就是通常所说的负面测试的测试用例。我们写出的函数除了要顺利地完成要求的功能之外，当输入不符合要求的时候还能做出合理的错误处理。在设计把字符串转换成整数的函数的时候，我们就要考虑当输入的字符串不是一个数字，比如”1a2b3c”，我们怎么告诉函数的调用者这个输入是非法的。 前面我们说的都是要全面考虑当前需求对应的各种可能输入。在软件开发过程中，永远不变的就是需求会一直改变。如果我们在面试的时候写出的代码能够把将来需求可能的变化都考虑进去，在需求发生变化的时候能够尽量减少代码改动的风险，那我们就向面试官展示了自己对程序可扩展性和可维护性的理解，通过面试就是水到渠成的事情了。请参考面试题14“调整数组顺序使奇数位于偶数前面”中关于可扩展性和可维护性的讨论。 2．3种错误处理的方法 通常我们有3种方式把错误信息传递给函数的调用者。第一种方式是函数用返回值来告知调用者是否出错。比如很多Windows的API就是这个类型。Windows中很多API的返回值为0表示API调用成功，而返回值不为0表示在API调用的过程中出错了。微软为不同的非零返回值定义了不同的意义，调用者可以根据这些返回值判断出错的原因。这种方式最大的问题是使用不便，因为函数不能直接把计算结果通过返回值赋值给其他变量，同时也不能把这个函数计算的结果直接作为参数传递给其他函数。 第二种方式是当发生错误时设置一个全局变量。此时我们可以在返回值中传递计算结果了。这种方法比第一种方法使用起来更加方便，因为调用者可以直接把返回值赋值给其他变量或者作为参数传递给其他函数。Windows的很多API运行出错之后，也会设置一个全局变量。我们可以通过调用函数GetLastError分析这个表示错误的全局变量，从而得知出错的原因。但这个方法有个问题：调用者很容易就会忘记去检查全局变量，因此在调用出错的时候忘记做相应的错误处理，从而留下安全隐患。 第三种方式是异常。当函数运行出错的时候，我们就抛出一个异常，我们还可以根据不同的出错原因定义不同的异常类型。因此函数的调用者根据异常的类型就能知道出错的原因，从而做相应的处理。另外，我们能显式划分程序正常运行的代码块（try模块）和处理异常的代码块（catch模块），逻辑比较清晰。异常在高级语言如C#中是强烈推荐的错误处理方式，但有些早期的语言比如C语言还不支持异常。另外，当抛出异常的时候，程序的执行会打乱正常的顺序，对程序的性能有很大的影响。 上述3种错误处理的方式各有其优缺点（如表3.1所示）。那么，面试的时候我们该采用哪种方式呢？这要看面试官的需求。在听到面试官的题目之后，我们要尽快分析出可能存在哪些非法的输入，并和面试官讨论该如何处理这些非法输入。 表3.1 返回值、全局变量和异常三种错误处理方式的优缺点比较  面试题11：数值的整数次方 题目：实现函数double Power（double base, int exponent），求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。 我们都知道在C语言的库中有一个pow函数可以用来求乘方，本题要求实现类似于pow的功能。要求实现特定库函数（特别是处理数值和字符串的函数）的功能，是一类常见的面试题。在本书收集的面试题中，除了这个题目外，还有面试题49“把字符串转换成整数”要求实现库函数atoi的功能。这就要求我们平时编程的时候除了能熟练使用库函数外，更重要的是要理解库函数的实现原理。 自以为题目简单的解法 由于不需要考虑大数问题，这道题看起来很简单，可能不少应聘者在看到题目30秒后就能写出如下的代码：  不过遗憾的是，写得快不一定就能得到面试官的青睐，因为面试官会问要是输入的指数（exponent）小于1即是零和负数的时候怎么办？上面的代码完全没有考虑，只包括了指数是正数的情况。 全面但不够高效的解法，我们离Offer已经很近了 我们知道当指数为负数的时候，可以先对指数求绝对值，然后算出次方的结果之后再取倒数。既然有求倒数，我们很自然就要想到有没有可能对0求倒数，如果对0求倒数怎么办？当底数（base）是零且指数是负数的时候，如果不做特殊处理，就会出现对0求倒数从而导致程序运行出错。怎么告诉函数的调用者出现了这种错误？前面提到我们可以采用3种方法：返回值、全局代码和异常。面试的时候可以向面试官阐述每种方法的优缺点，然后一起讨论决定选用哪种方式。 最后需要指出的是，由于0的0次方在数学上是没有意义的，因此无论是输出0还是1都是可以接受的，但这都需要和面试官说清楚，表明我们已经考虑到这个边界值了。 有了这些相对而言已经全面很多的考虑，我们就可以把最初的代码修改如下：  在上述代码中我们采用全局变量来标识是否出错。如果出错了，则返回的值是0。但为了区分是出错的时候返回的0，还是底数为0的时候正常运行返回的0，我们还定义了一个全局变量g\_InvalidInput。当出错时，这个变量被设为true，否则为false。这样做的好处是，我们可以把返回值直接传递给其他变量，比如写double result=Power（2,3），也可以把函数的返回值直接传递给其他需要double型参数的函数。但缺点是这个函数的调用者有可能会忘记去检查g\_InvalidInput以判断是否出错，留下了安全隐患。由于有优点也有缺点，因此我们在写代码之前要和面试官讨论采用哪种出错处理方式最合适。 一个细节值得我们注意：在判断底数base是不是等于0时，不能直接写base==0，这是因为在计算机内表示小数时（包括float和double型小数）都有误差。判断两个小数是否相等，只能判断它们之差的绝对值是不是在一个很小的范围内。如果两个数相差很小，就可以认为它们相等。这就是我们定义函数equal的原因。 面试小提示： 由于计算机表示小数（包括float和double型小数）都有误差，我们不能直接用等号（==）判断两个小数是否相等。如果两个小数的差的绝对值很小，比如小于0.0000001，就可以认为它们相等。 此时我们考虑得已经很周详了，已经能够达到很多面试官的要求了。但是如果我们碰到的面试官是一个在效率上追求完美的人，那么他有可能会提醒我们函数PowerWithUnsignedExponent还有更快的办法。 全面又高效的解法，确保我们能拿到Offer 如果输入的指数exponent为32，我们在函数PowerWithUnsignedExponent的循环中需要做31次乘法。但我们可以换一种思路考虑：我们的目标是求出一个数字的32次方，如果我们已经知道了它的16次方，那么只要在16次方的基础上再平方一次就可以了。而16次方是8次方的平方。这样以此类推，我们求32次方只需要做5次乘法：先求平方，在平方的基础上求4次方，在4次方的基础上求8次方，在8次方的基础上求16次方，最后在16次方的基础上求32次方。 也就是说，我们可以用如下公式求a的n次方：  这个公式看起来是不是眼熟？我们前面在介绍用O（logn）时间求斐波那契数列时，就讨论过这个公式，这个公式很容易就能用递归来实现。新的PowerWithUnsignedExponent代码如下：  最后再提醒一个细节：我们用右移运算符代替了除以2，用位与运算符代替了求余运算符（%）来判断一个数是奇数还是偶数。位运算的效率比乘除法及求余运算的效率要高很多。既然要优化代码，我们就把优化做到极致。 在面试的时候，我们可以主动提醒面试官注意代码中的两处细节（判断base是否等于0和用位运算替代乘除法及求余运算），让他知道我们对编程的细节很重视。细节很重要，因为细节决定成败，一两个好的细节说不定就能让面试官下定决心给我们Offer。 源代码： 本题完整的源代码详见11\_Power项目。 测试用例： 把底数和指数分别设为正数、负数和零。 本题考点： ● 考查思维的全面性。这个问题本身不难，但能顺利通过的应聘者不是很多。有很多人会忽视底数为0而指数为负数时的错误处理。 ● 对效率要求比较高的面试官还会考查应聘者快速做乘方的能力。 面试题12：打印1到最大的n位数 题目：输入数字n，按顺序打印出从1最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数即999。 跳进面试官陷阱 这个题目看起来很简单。我们看到这个问题之后，最容易想到的办法是先求出最大的n位数，然后用一个循环从1开始逐个打印。于是我们很容易就能写出如下的代码：  初看之下好像没有问题，但如果仔细分析这个问题，我们就能注意到面试官没有规定n的范围。当输入的n很大的时候，我们求最大的n位数是不是用整型（int）或者长整型（long long）都会溢出？也就是说我们需要考虑大数问题。这是面试官在这道题里设置的一个大陷阱。 在字符串上模拟数字加法的解法，绕过陷阱才能拿到Offer 经过前面的分析，我们很自然地想到解决这个问题需要表达一个大数。最常用也是最容易的方法是用字符串或者数组表达大数。接下来我们用字符串来解决大数问题。 用字符串表示数字的时候，最直观的方法就是字符串里每个字符都是’0’到’9’之间的某一个字符，用来表示数字中的一位。因为数字最大是n位的，因此我们需要一个长度为n＋1的字符串（字符串中最后一个是结束符号’\\0’）。当实际数字不够n位的时候，在字符串的前半部分补0。 首先我们把字符串中的每一个数字都初始化为’0’，然后每一次为字符串表示的数字加1，再打印出来。因此我们只需要做两件事：一是在字符串表达的数字上模拟加法，二是把字符串表达的数字打印出来。 基于上面的分析，我们可以写出如下代码：  在上面的代码中，函数Increment实现在表示数字的字符串number上增加1，而函数PrintNumber打印出number。这两个看似简单的函数都暗藏着小小的玄机。 我们需要知道什么时候停止在number上增加1，即什么时候到了最大的n位数“999…99”（n个9）。一个最简单的办法是每次递增之后，都调用库函数strcmp比较表示数字的字符串number和最大的n位数“999…99”，如果相等则表示已经到了最大的n位数并终止递增。虽然调用strcmp很简单，但对于长度为n的字符串，它的时间复杂度为O（n）。 我们注意到只有对“999…99”加1的时候，才会在第一个字符（下标为0）的基础上产生进位，而其他所有情况都不会在第一个字符上产生进位。因此当我们发现在加1时第一个字符产生了进位，则已经是最大的n位数，此时Increment返回true，因此函数Print1ToMaxOfNDigits中的while循环终止。如何在每一次增加1之后快速判断是不是到了最大的n位数是本题的一个小陷阱。下面是Increment函数的参考代码，它实现了用O（1）时间判断是不是已经到了最大的n位数：  接下来我们再考虑如何打印用字符串表示的数字。虽然库函数printf可以很方便就能打印一个字符串，但在本题中调用printf并不是最合适的解决方案。前面我们提到，当数字不够n位的时候，我们在数字的前面补0，打印的时候这些补位的0不应该打印出来。比如输入3的时候，数字98用字符串表示成“098”。如果直接打印出098，就不符合我们的习惯。为此我们定义了函数PrintNumber，在这个函数里，我们只有在碰到第一个非0的字符之后才开始打印，直至字符串的结尾。能不能按照我们的阅读习惯打印数字，是面试官设置的另外一个小陷阱。实现代码如下：  把问题转换成数字排列的解法，递归让代码更简洁 上述思路虽然比较直观，但由于模拟了整数的加法，代码有点长。要在面试短短几十分钟时间里完整正确地写出这么长的代码，对很多应聘者而言不是一件容易的事情。接下来我们换一种思路来考虑这个问题。如果我们在数字前面补0的话，就会发现n位所有十进制数其实就是n个从0到9的全排列。也就是说，我们把数字的每一位都从0到9排列一遍，就得到了所有的十进制数。只是我们在打印的时候，数字排在前面的0我们不打印出来罢了。 全排列用递归很容易表达，数字的每一位都可能是0～9中的一个数，然后设置下一位。递归结束的条件是我们已经设置了数字的最后一位。  函数PrintNumber和前面第二种思路中的一样，这里就不再重复了。 源代码： 本题完整的源代码详见12\_Print1ToMaxOfNDigits项目。 测试用例： ● 功能测试（输入1、2、3……）。 ● 特殊输入测试（输入-1、0）。 本题考点： ● 考查解决大数问题的能力。面试官出这个题目的时候，他期望应聘者能意识到这是一个大数问题，同时还期待应聘者能定义合适的数据表示方式来解决大数问题。 ● 如果应聘者采用第一种思路即在数上加1逐个打印的思路，面试官会关注他判断是否已经到了最大的n位数时采用的方法。应聘者要注意到不同方法的时间效率相差很大。 ● 如果应聘者采用第二种思路，面试官还将考查他用递归方法解决问题的能力。 ● 面试官还将关注应聘者打印数字时会不会打印出位于数字最前面的0。这里能体现出应聘者在设计开发软件时是不是会考虑用户的使用习惯。通常我们的软件设计和开发需要符合大部分用户的人机交互习惯。 本题扩展： 在前面的代码中，我们都是用一个char型字符表示十进制数字的一位。8个bit的char型字符最多能表示256个字符，而十进制数字只有0～9的10个数字。因此用char型字符串来表示十进制的数字并没有充分利用内存，有一些浪费。有没有更高效的方式来表示大数？ 相关题目： 定义一个函数，在该函数中可以实现任意两个整数的加法。由于没有限定输入两个数的大小范围，我们也要把它当做大数问题来处理。在前面的代码的第一个思路中，实现了在字符串表示的数字上加1的功能，我们可以参考这个思路实现两个数字的相加功能。另外还有一个需要注意的问题：如果输入的数字中有负数，我们应该怎么去处理？ 面试小提示： 如果面试题是关于n位的整数并且没有限定n的取值范围，或者是输入任意大小的整数，那么这个题目很有可能是需要考虑大数问题的。字符串是一个简单、有效的表示大数的方法。 面试题13：在O（1）时间删除链表结点 题目：给定单向链表的头指针和一个结点指针，定义一个函数在O（1）时间删除该结点。链表结点与函数的定义如下：  在单向链表中删除一个结点，最常规的做法无疑是从链表的头结点开始，顺序遍历查找要删除的结点，并在链表中删除该结点。 比如在图3.3（a）所示的链表中，我们想删除结点i，可以从链表的头结点a开始顺序遍历，发现结点h的m\_pNext指向要删除的结点i，于是我们可以把结点h的m\_pNext指向i的下一个结点即结点j。指针调整之后，我们就可以安全地删除结点i并保证链表没有断开（如图3.3（b）所示）。这种思路由于需要顺序查找，时间复杂度自然就是O（n）了。  图3.3 在链表中删除一个结点的两种方法 注：（a）一个链表。（b）删除结点i之前，先从链表的头结点开始遍历到i前面的一个结点h，把h的m\_pNext指向i的下一个结点j，再删除结点i。（c）把结点j的内容复制覆盖结点i，接下来再把结点i的m\_pNext指向j的下一个结点之后删除结点j。这种方法不用遍历链表上结点i前面的结点。 之所以需要从头开始查找，是因为我们需要得到将被删除的结点的前面一个结点。在单向链表中，结点中没有指向前一个结点的指针，所以只好从链表的头结点开始顺序查找。 那是不是一定需要得到被删除的结点的前一个结点呢？答案是否定的。我们可以很方便地得到要删除的结点的一下结点。如果我们把下一个结点的内容复制到需要删除的结点上覆盖原有的内容，再把下一个结点删除，那是不是就相当于把当前需要删除的结点删除了？ 我们还是以前面的例子来分析这种思路。我们要删除结点i，先把i的下一个结点j的内容复制到i，然后把i的指针指向结点j的下一个结点。此时再删除结点j，其效果刚好是把结点i给删除了（如图3.3（c）所示）。 上述思路还有一个问题：如果要删除的结点位于链表的尾部，那么它就没有下一个结点，怎么办？我们仍然从链表的头结点开始，顺序遍历得到该结点的前序结点，并完成删除操作。 最后需要注意的是，如果链表中只有一个结点，而我们又要删除链表的头结点（也是尾结点），此时我们在删除结点之后，还需要把链表的头结点设置为NULL。 有了这些思路，我们就可以动手写代码了。下面是这种思路的参考代码：  接下来我们分析这种思路的时间复杂度。对于n－1个非尾结点而言，我们可以在O（1）时把下一个结点的内存复制覆盖要删除的结点，并删除下一个结点；对于尾结点而言，由于仍然需要顺序查找，时间复杂度是O（n）。因此总的平均时间复杂度是\[（n－1）\*O（1）＋O（n）\]/n，结果还是O（1），符合面试官的要求。 值得注意的是，上述代码仍然不是完美的代码，因为它基于一个假设：要删除的结点的确在链表中。我们需要O（n）的时间才能判断链表中是否包含某一结点。受到O（1）时间的限制，我们不得不把确保结点在链表中的责任推给了函数DeleteNode的调用者。在面试的时候，我们可以和面试官讨论这个假设，这样面试官就会觉得我们考虑问题非常全面。 源代码： 本题完整的源代码详见13\_DeleteNodeInList项目。 测试用例： ● 功能测试（从有多个结点的链表的中间删除一个结点，从有多个结点的链表中删除头结点，从有多个结点的链表中删除尾结点，从只有一个结点的链表中删除唯一的结点）。 ● 特殊输入测试（指向链表头结点指针的为NULL指针，指向要删除的结点为NULL指针）。 本题考点： ● 考查应聘者对链表的编程能力。 ● 考查应聘者的创新思维能力。这道题要求应聘者打破常规的思维模式。当我们想删除一个结点时，并不一定要删除这个结点本身。可以先把下一个结点的内容复制出来覆盖被删除结点的内容，然后把下一个结点删除。这种思路不是很容易想到的。 ● 考查应聘者思维的全面性。即使应聘者想到删除下一个结点这个办法，也未必能通过这轮面试。应聘者要全面考虑到删除的结点位于链表的尾部及输入的链表只有一个结点这些特殊情况。 面试题14：调整数组顺序使奇数位于偶数前面 题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。 如果不考虑时间复杂度，最简单的思路应该是从头扫描这个数组，每碰到一个偶数时，拿出这个数字，并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位，这时把该偶数放入这个空位。由于每碰到一个偶数就需要移动O（n）个数字，因此总的时间复杂度是O（n2）。但是，这种方法不能让面试官满意。不过如果我们在听到题目之后马上能说出这个解法，面试官至少会觉得我们的思维非常敏捷。 只完成基本功能的解法，仅适用于初级程序员 这个题目要求把奇数放在数组的前半部分，偶数放在数组的后半部分，因此所有的奇数应该位于偶数的前面。也就是说我们在扫描这个数组的时候，如果发现有偶数出现在奇数的前面，我们可以交换它们的顺序，交换之后就符合要求了。 因此我们可以维护两个指针，第一个指针初始化时指向数组的第一个数字，它只向后移动；第二个指针初始化时指向数组的最后一个数字，它只向前移动。在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，我们就交换这两个数字。 下面以一个具体的例子比如输入数组{1,2,3,4,5}来分析这种思路。在初始化时，把第一个指针指向数组第一个数字1，而把第二个指针指向最后一个数字5（如图3.4（a）所示）。第一个指针指向的数字1是一个奇数，不需要处理，我们把第一个指针向后移动，直到碰到一个偶数2。此时第二个指针已经指向了奇数，因此不需要移动。此时两个指针指向的位置如图3.4（b）所示。这个时候我们发现偶数2位于奇数5的前面，符合我们的交换条件，于是交换两个指针指向的数字（如图3.4（c）所示）。 接下来我们继续向后移第一个指针，直到碰到下一个偶数4，并向前移动第二个指针，直到碰到第一个奇数3（如图3.4（d）所示）。我们发现第二个指针已经在第一个指针的前面了，表示所有的奇数都已经在偶数的前面了。此时的数组是{1,5,3,4,2}，的确是奇数位于数组的前半部分而偶数位于后半部分。  图3.4 调整数组{1,2,3,4,5} 使得奇数位于偶数前面的过程 注：（a）把第一个指针指向数组的第一个数字，第二个指针指向最后一个数字。（b）向后移动第一个指针直至它指向偶数2，此时第二个指针指向奇数5，不需要移动。（c）交换两个指针指向的数字。（d）向后移动第一个指针直至它指向偶数4，向前移动第二个指针直至它指向奇数3。由于第二个指针移到了第一个指针的前面，表明所有的奇数都位于偶数的前面。 基于这个分析，我们可以写出如下代码：  考虑可扩展性的解法，能秒杀Offer 如果是面试应届毕业生或者工作时间不长的程序员，面试官会满意前面的代码。但如果应聘者申请的是资深的开发职位，那面试官可能会接着问几个问题。 面试官：如果把题目改成把数组中的数按照大小分为两部分，所有负数都在非负数的前面，该怎么做？ 应聘者：这很简单，可以重新定义一个函数。在新的函数里，只要修改第二个和第三个while循环中的判断条件就行了。 面试官：如果再把题目改改，变成把数组中的数分为两部分，能被3整除的数都在不能被3整除的数的前面。怎么办？ 应聘者：我们还是可以定义一个新的函数。在这个函数中…… 面试官：（打断应聘者的话）难道就没有更好的办法？ 这个时候应聘者应该要反应过来，面试官期待我们提供的不仅仅是解决一个问题的办法，而是解决一系列同类型问题的通用办法。这就是面试官在考查我们对扩展性的理解，即希望我们能够给出一个模式，在这个模式下能够很方便地把已有的解决方案扩展到同类型的问题上去。 回到面试官新提出的两个问题上来。我们发现要解决这两个新的问题，其实只需要修改函数ReorderOddEven中的两处判断的标准，而大的逻辑框架完全不需要改动。因此我们可以把这个逻辑框架抽象出来，而把判断的标准变成一个函数指针，也就是用一个单独的函数来判断数字是不是符合标准。这样我们就把整个函数解耦成两部分：一是判断数字应该在数组前半部分还是后半部分的标准，二是拆分数组的操作。于是我们可以写出下面的代码：  在上面的代码中，函数Reorder根据func的标准把数组pData分成两部分；而函数isEven则是一个具体的标准，即判断一个数是不是偶数。有了这两个函数，我们可以很方便地把数组中的所有奇数移到偶数的前面。实现代码如下：  如果把问题改成把数组中的负数移到非负数的前面，或者把能被3整除的数移到不能被3整数的数的前面，都只需定义新的函数来确定分组的标准，而函数Reorder不需要做任何改动。也就是说解耦的好处就是提高了代码的重用性，为功能扩展提供了便利。 源代码： 本题完整的源代码详见14\_ReorderArray项目。 测试用例： ● 功能测试（输入数组中的奇数、偶数交替出现，输入的数组中所有偶数都出现在奇数的前面，输入的数组中所有奇数都出现在偶数的前面）。 ● 特殊输入测试（输入NULL指针、输入的数组只包含一个数字）。 本题考点： ● 考查应聘者的快速思维能力。要在短时间内按照要求把数组分隔成两部分，不是一件容易的事情，需要较快的思维能力。 ● 对于已经工作过几年的应聘者，面试官还将考查其对扩展性的理解，要求应聘者写出的代码具有可重用性。 3.4 代码的鲁棒性 鲁棒是英文Robust的音译，有时也翻译成健壮性。所谓的鲁棒性是指程序能够判断输入是否合乎规范要求，并对不合要求的输入予以合理的处理。 容错性是鲁棒性的一个重要体现。不鲁棒的软件在发生异常事件的时候，比如用户输入错误的用户名、试图打开的文件不存在或者网络不能连接，就会出现不可预见的诡异行为，或者干脆整个软件崩溃。这样的软件对于用户而言，不亚于一场灾难。 由于鲁棒性对软件开发非常重要，面试官在招聘的时候对应聘者写出的代码是否鲁棒也非常关注。提高代码的鲁棒性的有效途径是进行防御性编程。防御性编程是一种编程习惯，是指预见在什么地方可能会出现问题，并为这些可能出现的问题制定处理方式。比如试图打开文件时发现文件不存在，我们可以提示用户检查文件名和路径；当服务器连接不上时，我们可以试图连接备用服务器等。这样当异常情况发生时，软件的行为也尽在我们的掌握之中，而不至于出现不可预见的事情。 在面试时，最简单也最实用的防御性编程就是在函数入口添加代码以验证用户输入是否符合要求。通常面试要求的是写一两个函数，我们需要格外关注这些函数的输入参数。如果输入的是一个指针，那指针是空指针怎么办？如果输入的是一个字符串，那么字符串的内容为空怎么办？如果能把这些问题都提前考虑到，并做相应的处理，那么面试官就会觉得我们有防御性编程的习惯，能够写出鲁棒的软件。 当然并不是所有与鲁棒性相关的问题都只是检查输入的参数这么简单。我们看到问题的时候，要多问几个“如果不……那么……”这样的问题。比如面试题15“链表中倒数第k个结点”，这里隐含着一个条件就是链表中结点的个数大于k。我们就要问如果链表中的结点的数目不是大于k个，那么代码会出什么问题？这样的思考方式能够帮助我们发现潜在的问题并提前解决问题。这比让面试官发现问题之后我们再去慌忙分析代码查找问题的根源要好得多。 面试题15：链表中倒数第k个结点 题目：输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。 链表结点定义如下：  为了得到倒数第k个结点，很自然的想法是先走到链表的尾端，再从尾端回溯k步。可是我们从链表结点的定义可以看出本题中的链表是单向链表，单向链表的结点只有从前往后的指针而没有从后往前的指针，因此这种思路行不通。 既然不能从尾结点开始遍历这个链表，我们还是把思路回到头结点上来。假设整个链表有n个结点，那么倒数第k个结点就是从头结点开始的第n－k＋1个结点。如果我们能够得到链表中结点的个数n，那我们只要从头结点开始往后走n－k＋1步就可以了。如何得到结点数n？这个不难，只需要从头开始遍历链表，每经过一个结点，计数器加1就行了。 也就是说我们需要遍历链表两次，第一次统计出链表中结点的个数，第二次就能找到倒数第k个结点。但是当我们把这个思路解释给面试官之后，他会告诉我们他期待的解法只需要遍历链表一次。 为了实现只遍历链表一次就能找到倒数第k个结点，我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k－1，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k－1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。 下面以在有6个结点的链表中找倒数第3个结点为例分析这个思路的过程。首先用第一个指针从头结点开始向前走两（2=3－1）步到达第3个结点（如图3.5（a）所示）。接着我们把第二个指针初始化指向链表的第一个结点（如图3.5（b）所示）。最后让两个指针同时向前遍历，当第一个指针到达链表的尾结点时，第二个指针指向的刚好就是倒数第3个结点（如图3.5（c）所示）。  图3.5 在有6个结点的链表上找倒数第3个结点的过程 注：（a）第一个指针在链表上走两步。（b）把第二个指针指向链表的头结点。（c）两个指针一同沿着链表向前走。当第一个指针指向链表的尾结点时，第二个指针指向倒数第3个结点。 想清楚这个思路之后，很多人很快就能写出如下的代码：  有不少人在面试之前从网上看到过用两个指针遍历的思路来解这道题，因此听到面试官问这道题，他们心中一阵窃喜，很快就能写出代码。可是几天之后他们等来的不是Offer，却是拒信，于是百思不得其解。其实原因很简单，就是自己写的代码不够鲁棒。以上面的代码为例，面试官可以找出3种办法让这段代码崩溃： 输入的pListHead为空指针。由于代码会试图访问空指针指向的内存，程序崩溃。 输入的以pListHead为头结点的链表的结点总数少于k。由于在for循环中会在链表上向前走k－1步，仍然会由于空指针造成程序崩溃。 输入的参数k为0。由于k是一个无符号整数，那么在for循环中k－1得到的将不是-1，而是4294967295（无符号的0xFFFFFFFF）。因此for循环执行的次数远远超出我们的预计，同样也会造成程序崩溃。 这么简单的代码却存在3个潜在崩溃的风险，我们可以想象当面试官看到这样的代码时会有什么样的心情，最终他给出的是拒信而不是Offer虽是意料之外但也在情理之中。 面试小提示： 面试过程中写代码要特别注意鲁棒性。如果写出的代码存在多处崩溃的风险，那我们很有可能和Offer失之交臂。 针对前面指出的3个问题，我们要分别处理。如果输入的链表头指针为NULL，那么整个链表为空，此时查找倒数第k个结点自然应该返回NULL。如果输入的k是0，也就是试图查找倒数第0个结点，由于我们计数是从1开始的，因此输入0没有实际意义，也可以返回NULL。如果链表的结点数少于k，在for循环中遍历链表可能会出现指向NULL的m\_pNext，因此我们在for循环中应该加一个if判断。修改之后的代码如下：  源代码： 本题完整的源代码详见15\_KthNodeFromEnd项目。 测试用例： ● 功能测试（第k个结点在链表的中间，第k个结点是链表的头结点，第k个结点是链表的尾结点）。 ● 特殊输入测试（链表头结点为NULL指针，链表的结点总数少于k，k等于0）。 本题考点： ● 考查对链表的理解。 ● 考查代码的鲁棒性。鲁棒性是解决这道题的关键所在。如果应聘者写出的代码有着多处崩溃的潜在风险，那么他是很难通过这轮面试的。 相关题目： ● 求链表的中间结点。如果链表中结点总数为奇数，返回中间结点；如果结点总数是偶数，返回中间两个结点的任意一个。为了解决这个问题，我们也可以定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个指针一次走两步。当走得快的指针走到链表的末尾时，走得慢的指针正好在链表的中间。 ● 判断一个单向链表是否形成了环形结构。和前面的问题一样，定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的末尾（m\_pNext指向NULL）都没有追上第一个指针，那么链表就不是环形链表。 举一反三： 当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些（比如一次在链表上走两步），或者让它先在链表上走若干步。 面试题16：反转链表 题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。链表结点定义如下：  解决与链表相关的问题总是有大量的指针操作，而指针操作的代码总是容易出错的。很多面试官喜欢出链表相关的问题，就是想通过指针操作来考查应聘者的编码功底。为了避免出错，我们最好先进行全面的分析。在实际软件开发周期中，设计的时间通常不会比编码的时间短。在面试的时候我们不要急于动手写代码，而是一开始仔细分析和设计，这将会给面试官留下很好的印象。与其很快写出一段漏洞百出的代码，倒不如仔细分析再写出鲁棒的代码。 为了正确地反转一个链表，需要调整链表中指针的方向。为了将调整指针这个复杂的过程分析清楚，我们可以借助图形来直观地分析。在图3.6（a）所示的链表中，h、i和j是3个相邻的结点。假设经过若干操作，我们已经把结点h之前的指针调整完毕，这些结点的m\_pNext都指向前面一个结点。接下来我们把i的m\_pNext指向h，此时的链表结构如图3.6（b）所示。  图3.6 反转链表中结点的m\_pNext指针导致链表出现断裂 注：（a）一个链表。（b）把i之前所有的结点的m\_pNext都指向前一个结点，导致链表在结点i、j之间断裂。 不难注意到，由于结点i的m\_pNext指向了它的前一个结点，导致我们无法在链表中遍历到结点j。为了避免链表在结点i处断开，我们需要在调整结点i的m\_pNext之前，把结点j保存下来。 也就是说我们在调整结点i的m\_pNext指针时，除了需要知道结点i本身之外，还需要i的前一个结点h，因为我们需要把结点i的m\_pNext指向结点h。同时，我们还事先需要保存i的一个结点j，以防止链表断开。因此相应地我们需要定义3个指针，分别指向当前遍历到的结点、它的前一个结点及后一个结点。 最后我们试着找到反转后链表的头结点。不难分析出反转后链表的头结点是原始链表的尾结点。什么结点是尾结点？自然是m\_pNext为NULL的结点。 有了前面的分析，我们不难写出如下代码：  在面试的过程中，我们发现应聘者的代码中经常出现如下3种问题： ● 输入的链表头指针为NULL或者整个链表只有一个结点时，程序立即崩溃。 ● 反转后的链表出现断裂。 ● 返回的反转之后的头结点不是原始链表的尾结点。 在实际面试的时候，不同应聘者的思路各不相同，因此写出的代码也不一样。那么应聘者如何才能及时发现并纠正代码中的问题，以确保不犯上述错误呢？一个很好的办法就是提前想好测试用例。在写出代码之后，立即用事先准备好的测试用例检查测试。如果面试是以手写代码的方式，那也要在心里默默运行代码做单元测试。只有确保代码通过测试之后，再提交面试官。我们要记住一点：自己多花时间找出问题并修正问题，比在面试官找出问题之后再去慌慌张张修改代码要好得多。其实面试官检查应聘者代码的方法也是用他事先准备好的测试用例来测试。如果应聘者能够想到这些测试用例，并用它们来检查测试自己的代码，那就能保证有备无患、万无一失了。 以这道题为例，我们至少应该想到几类测试用例对代码做功能测试： ● 输入的链表头指针是NULL。 ● 输入的链表只有一个结点。 ● 输入的链表有多个结点。 如果我们确信代码能够通过这3类测试用例的测试，那我们就有很大的把握能够通过这轮面试了。 源代码： 本题完整的源代码详见16\_ReverseList项目。 测试用例： ● 功能测试（输入的链表含有多个结点，链表中只有一个结点）。 ● 特殊输入测试（链表头结点为NULL指针）。 本题考点： ● 考查应聘者对链表、指针的编程能力。 ● 特别注重考查应聘者思维的全面性及写出来的代码的鲁棒性。 本题扩展： 用递归实现同样的反转链表的功能。 面试题17：合并两个排序的链表 题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如输入图3.7中的链表1和链表2，则合并之后的升序链表如链表3所示。链表结点定义如下：   图3.7 合并两个排序链表的过程 注：链表1和链表2是两个递增排序的链表，合并这两个链表得到升序链表为链表3。 这是一个经常被各公司采用的面试题。在面试过程中，我们发现应聘者最容易犯两种错误：一是在写代码之前没有对合并的过程想清楚，最终合并出来的链表要么中间断开了要么并没有做到递增排序；二是代码在鲁棒性方面存在问题，程序一旦有特殊的输入（如空链表）就会崩溃。接下来分析如何解决这两个问题。 首先分析合并两个链表的过程。我们的分析从合并两个链表的头结点开始。链表1的头结点的值小于链表2的头结点的值，因此链表1的头结点将是合并后链表的头结点（如图3.8（a）所示）。  图3.8 合并两个递增链表的过程 注：（a）链表1的头结点的值小于链表2的头结点的值，因此链表1的头结点是合并后链表的头结点。（b）在剩余的结点中，链表2的头结点的值小于链表1的头结点的值，因此链表2的头结点是剩余结点的头结点，把这个结点和之前已经合并好的链表的尾结点链接起来。 我们继续合并两个链表中剩余的结点（图3.8中虚线框中的链表）。在两个链表中剩下的结点依然是排序的，因此合并这两个链表的步骤和前面的步骤是一样的。我们还是比较两个头结点的值。此时链表2的头结点的值小于链表1的头结点的值，因此链表2的头结点的值将是合并剩余结点得到的链表的头结点。我们把这个结点和前面合并链表时得到的链表的尾结点（值为1的结点）链接起来，如图3.8（b）所示。 当我们得到两个链表中值较小的头结点并把它链接到已经合并的链表之后，两个链表剩余的结点依然是排序的，因此合并的步骤和之前的步骤是一样的。这就是典型的递归的过程，我们可以定义递归函数完成这一合并过程。 接下来我们来解决鲁棒性的问题。每当代码试图访问空指针指向的内存时程序就会崩溃，从而导致鲁棒性问题。在本题中一旦输入空的链表就会引入空的指针，因此我们要对空链表单独处理。当第一个链表是空链表，也就是它的头结点是一个空指针时，那么把它和第二个链表合并，显然合并的结果就是第二个链表。同样，当输入的第二个链表的头结点是空指针的时候，我们把它和第一个链表合并得到的结果就是第一个链表。如果两个链表都是空链表，合并的结果是得到一个空链表。 在我们想清楚合并的过程，并且知道哪些输入可能会引起鲁棒性问题之后，就可以动手写代码了。下面是一段参考代码：  源代码： 本题完整的源代码详见17\_MergeSortedLists项目。 测试用例： ● 功能测试（输入的两个链表有多个结点，结点的值互不相同或者存在值相等的多个结点）。 ● 特殊输入测试（两个链表的一个或者两个头结点为NULL指针、两个链表中只有一个结点）。 本题考点： ● 考查应聘者分析问题的能力。解决这个问题需要大量的指针操作，应聘者如果没有透彻地分析问题形成清晰的思路，那么他很难写出正确的代码。 ● 考查应聘者能不能写出鲁棒的代码。由于有大量指针操作，应聘者如果稍有不慎就会在代码中遗留很多与鲁棒性相关的隐患。建议应聘者在写代码之前全面分析哪些情况会引入空指针，并考虑清楚怎么处理这些空指针。 面试题18：树的子结构 题目：输入两棵二叉树A和B，判断B是不是A的子结构。二叉树结点的定义如下：  例如图3.9中的两棵二叉树，由于A中有一部分子树的结构和B是一样的，因此B是A的子结构。  图3.9 两棵二叉树A和B，右边的树B是左边的树A的子结构 和链表相比，树中的指针操作更多也更复杂，因此与树相关的问题通常会比链表的要难。如果想加大面试的难度，树的题目是很多面试官的选择。面对着大量的指针操作，我们要更加小心，否则一不留神就会在代码中留下隐患。 现在回到这个题目本身。要查找树A中是否存在和树B结构一样的子树，我们可以分成两步：第一步在树A中找到和B的根结点的值一样的结点R，第二步再判断树A中以R为根结点的子树是不是包含和树B一样的结构。 以上面的两棵树为例来详细分析这个过程。首先我们试着在树A中找到值为8（树B的根结点的值）的结点。从树A的根结点开始遍历，我们发现它的根结点的值就是8。接着我们就去判断树A的根结点下面的子树是不是含有和树B一样的结构（如图3.10所示）。在树A中，根结点的左子结点的值是8，而树B的根结点的左子结点是9，对应的两个结点不同。  图3.10 树A的根结点和B的根结点的值相同，但树A的根结点下面（实线部分）的结构和树B的结构不一致 因此我们仍然需要遍历树A，接着查找值为8的结点。我们在树的第二层中找到了一个值为8的结点，然后进行第二步判断，即判断这个结点下面的子树是否含有和树B一样结构的子树（如图3.11所示）。于是我们遍历这个结点下面的子树，先后得到两个子结点9和2，这和树B的结构完全相同。此时我们在树A中找到了一个和树B的结构一样的子树，因此树B是树A的子结构。  图3.11 在树A中找到第二个值为8的结点，该结点下面（实线部分）的结构和B的结构一致 第一步在树A中查找与根结点的值一样的结点，这实际上就是树的遍历。对二叉树这种数据结构熟悉的读者自然知道可以用递归的方法去遍历，也可以用循环的方法去遍历。由于递归的代码实现比较简洁，面试时如果没有特别要求，我们通常都会采用递归的方式。下面是参考代码：  在面试的时候，我们一定要注意边界条件的检查，即检查空指针。当树A或树B为空的时候，定义相应的输出。如果没有检查并做相应的处理，程序非常容易崩溃，这是面试时非常忌讳的事情。 在上述代码中，我们递归调用HasSubtree遍历二叉树A。如果发现某一结点的值和树B的头结点的值相同，则调用DoesTree1HaveTree2，做第二步判断。 第二步是判断树A中以R为根结点的子树是不是和树B具有相同的结构。同样，我们也可以用递归的思路来考虑：如果结点R的值和树B的根结点不相同，则以R为根结点的子树和树B肯定不具有相同的结点；如果它们的值相同，则递归地判断它们各自的左右结点的值是不是相同。递归的终止条件是我们到达了树A或者树B的叶结点。参考代码如下：  我们注意到上述代码有多处判断一个指针是不是NULL，这样做是为了避免试图访问空指针而造成程序崩溃，同时也设置了递归调用的退出条件。在写遍历树的代码的时候一定要高度警惕，在每一处需要访问地址的时候都要问自己这个地址有没有可能是NULL，如果是NULL该怎么处理。 面试小提示： 二叉树相关的代码有大量的指针操作，每一次使用指针的时候，我们都要问自己这个指针有没有可能是NULL，如果是NULL该怎么处理。 为了确保自己的代码完整正确，在写出代码之后应聘者至少要用几个测试用例来检验自己的程序：树A和树B的头结点有一个或者两个都是空指针，在树A和树B中所有结点都只有左子结点或者右子结点，树A和树B的结点中含有分叉。只有这样才能写出让面试官满意的鲁棒代码。 源代码： 本题完整的源代码详见18\_SubstructureInTree项目。 测试用例： ● 功能测试（树A和树B都是普通的二叉树，树B是或者不是树A的子结构）。 ● 特殊输入测试（两棵二叉树的一个或者两个根结点为NULL指针、二叉树的所有结点都没有左子树或者右子树）。 本题考点： ● 考查对二叉树遍历算法的理解及递归编程能力。 ● 考查代码的鲁棒性。本题的代码中含有大量的指针操作，稍有不慎程序就会崩溃。应聘者需要采用防御性编程的方式，每次访问指针地址之前都要考虑这个指针有没有可能是NULL。 3.5 本章小结 本章从规范性、完整性和鲁棒性3个方面介绍了如何在面试时写出高质量的代码，如图3.12所示。  图3.12 从规范性、完整性和鲁棒性3个方面提高代码的质量 大多数面试都是要求应聘者在白纸或者白板上写代码。应聘者在编码的时候要注意规范性，尽量清晰地书写每个字母，通过缩进和对齐括号让代码布局合理，同时合理命名代码中的变量和函数。 最好在编码之前全面考虑所有可能的输入，确保写出的代码在完成了基本功能之外，还考虑了边界条件，并做好了错误处理。只有全面考虑到这3方面的代码才是完整的代码。 另外，要确保自己写出的程序不会轻易崩溃。平时在写代码的时候，应聘者最好养成防御式编程的习惯，在函数入口判断输入是否有效并对各种无效输入做好相应的处理。