3.3 代码的完整性

在面试过程中，面试官会非常关注应聘者考虑问题是否周全。面试官通过检查代码是否完整来考查应聘者的思维是否全面。通常面试官会检查应聘者的代码是否完成了基本功能、输入边界值是否能得到正确的输出、是否对各种不合规范的非法输入做出了合理的错误处理。

1．从3个方面确保代码的完整性

应聘者在写代码之前，首先要把可能的输入都想清楚，从而避免在程序中出现各种各样的质量漏洞。也就是说，在编码之前要考虑单元测试。如果能够设计全面的单元测试用例并在代码中体现出来，那么写出的代码自然也就是完整正确的了。通常我们可以从功能测试、边界测试和负面测试3个方面设计测试用例，以确保代码的完整性，如图3.2所示。

图3.2 从功能测试、边界测试和负面测试3个方面设计测试用例，以确保代码的完整性

首先要考虑的是普通功能测试的测试用例。我们首先要保证写出的代码能够完成面试官要求的基本功能。比如面试题要求完成的功能是把字符串转换成整数，我们就可以考虑输入字符串"123"来测试自己写的代码。这里要把零、正数和负数都考虑进去。

在考虑功能测试的时候，我们要尽量突破常规思维的限制。面试的时候我们经常受到惯性思维的限制，从而看不到更多的功能需求。比如面试题17“打印从1到最大的n位数”，很多人觉得这道题很简单。最大的3位数是999、最大的4位数是9999，这些数字很容易就能算出来。但是最大的n位数都能用int型表示吗？超出int的范围我们可以考虑long long类型，超出long long能够表示的范围呢？面试官是不是要求考虑任意大的数字？如果面试官确认题目要求的是任意大的数字，那么这道题目就是一个大数问题，此时我们需要特殊的数据结构来表示数字，比如用字符串或者数组来表示大的数字，以确保不会溢出。

其次需要考虑各种边界值的测试用例。很多时候我们的代码中都会有循环或者递归。如果我们的代码基于循环，那么结束循环的边界条件是否正确？如果基于递归，那么递归终止的边界值是否正确？这些都是边界测试时要考虑的用例。还是以字符串转换成整数的问题为例，我们写出的代码应该确保能够正确转换最大的正整数和最小的负整数。

最后还需要考虑各种可能的错误输入，也就是通常所说的负面测试的测试用例。我们写出的函数除了要顺利地完成要求的功能，当输入不符合要求的时候还能做出合理的错误处理。在设计把字符串转换成整数的函数的时候，我们就要考虑当输入的字符串不是一个数字时，比如"1a2b3c"，该怎么告诉函数的调用者这个输入是非法的。

前面所说的都是要全面考虑当前需求对应的各种可能输入。在软件开发过程中，永远不变的就是需求会一直改变。如果我们在面试的时候写出的代码能够把将来需求可能的变化都考虑进去，在需求发生变化的时候能够尽量减少代码改动的风险，那么我们就向面试官展示了自己对程序可扩展性和可维护性的理解，通过面试就是水到渠成的事情了。请参考面试题21“调整数组顺序使奇数位于偶数前面”中关于可扩展性和可维护性的讨论。

2．3种错误处理的方法

通常我们有3种方式把错误信息传递给函数的调用者。第一种方式是函数用返回值来告知调用者是否出错。比如很多Windows的API就是这个类型。在Windows中，很多API的返回值为0表示API调用成功，而返回值不为0表示在API的调用过程中出错了。微软为不同的非零返回值定义了不同的意义，调用者可以根据这些返回值判断出错的原因。这种方式最大的问题是使用不便，因为函数不能直接把计算结果通过返回值赋值给其他变量，同时也不能把这个函数计算的结果直接作为参数传递给其他函数。

第二种方式是当错误发生时设置一个全局变量。此时我们可以在返回值中传递计算结果了。这种方法比第一种方法使用起来更加方便，因为调用者可以直接把返回值赋值给其他变量或者作为参数传递给其他函数。Windows的很多API运行出错之后，也会设置一个全局变量。我们可以通过调用函数GetLastError分析这个表示错误的全局变量，从而得知出错的原因。但这种方法有一个问题：调用者很容易忘记检查全局变量，因此在调用出错的时候忘记进行相应的错误处理，从而留下安全隐患。

第三种方式是异常。当函数运行出错的时候，我们就抛出一个异常，还可以根据不同的出错原因定义不同的异常类型。因此，函数的调用者根据异常的类型就能知道出错的原因，从而做出相应的处理。另外，我们能显式划分程序正常运行的代码块（try模块）和处理异常的代码块（catch模块），逻辑比较清晰。异常在高级语言如C#中是强烈推荐的错误处理方式，但有些早期的语言如C语言还不支持异常。另外，在抛出异常的时候，程序的执行会打乱正常的顺序，对程序的性能有很大的影响。

上述3种错误处理的方式各有其优缺点，如表3.1所示。那么，面试的时候我们该采用哪种方式呢？这要看面试官的需求。在听到面试官的题目之后，我们要尽快分析出可能存在哪些非法的输入，并和面试官讨论该如何处理这些非法输入。

表3.1 返回值、全局变量和异常3种错误处理方式的优缺点比较

优 点 缺 点

返回值 和系统API一致 不能方便地使用计算结果

全局变量 能够方便地使用计算结果 用户可能会忘记检查全局变量

异常 可以为不同的出错原因定义不同的异常类型，逻辑清晰明了 有些语言不支持异常，抛出异常时对性能有负面影响

面试题16：数值的整数次方

题目：实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

我们都知道，在C语言的库中有一个pow函数可以用来求乘方，本题要求实现类似于pow的功能。要求实现特定库函数（特别是处理数值和字符串的函数）的功能是一类常见的面试题。在本书收集的面试题中，除这个题目外，还有面试题67“把字符串转换成整数”要求实现库函数atoi的功能。这就要求我们在平时编程的时候除了能熟练使用库函数，更重要的是要理解库函数的实现原理。

自以为题目简单的解法

由于不需要考虑大数问题，这道题看起来很简单，可能不少应聘者在看到题目30秒后就能写出如下代码：

double Power(double base, int exponent)

{

double result = 1.0;

for(int i = 1; i <= exponent; ++i)

result *= base;

return result;

}

不过遗憾的是，写得快不一定就能得到面试官的青睐，因为面试官会问如果输入的指数（exponent）小于1（零和负数）的时候怎么办？上面的代码完全没有考虑，只考虑了指数是正数的情况。

全面但不够高效的解法，我们离Offer已经很近了

我们知道，当指数为负数的时候，可以先对指数求绝对值，算出次方的结果之后再取倒数。既然要求倒数，我们很自然地想到有没有可能对0求倒数，如果对0求倒数该怎么办？当底数（base）是零且指数是负数的时候，如果不进行特殊处理，就会出现对0求倒数，从而导致程序运行出错。怎么告诉函数的调用者出现了这种错误？前面提到我们可以采用3种方法：返回值、全局变量和异常。面试的时候可以向面试官阐述每种方法的优缺点，然后一起讨论决定选用哪种方法。

最后需要指出的是，由于0的0次方在数学上是没有意义的，因此无论输出是0还是1都是可以接受的，但这都需要和面试官说清楚，表明我们已经考虑到这个边界值了。

有了这些相对而言已经全面很多的考虑，我们就可以把最初的代码修改如下：

bool g_InvalidInput = false;

double Power(double base, int exponent)

{

g_InvalidInput = false;

if(equal(base, 0.0) && exponent < 0)

{

g_InvalidInput = true;

return 0.0;

}

unsigned int absExponent = (unsigned int)(exponent);

if(exponent < 0)

absExponent = (unsigned int)(-exponent);

double result = PowerWithUnsignedExponent(base, absExponent);

if(exponent < 0)

result = 1.0 / result;

return result;

}

double PowerWithUnsignedExponent(double base, unsigned int exponent)

{

double result = 1.0;

for(int i = 1; i <= exponent; ++i)

result *= base;

return result;

}

在上述代码中，我们采用全局变量来标识是否出错。如果出错了，则返回的值是0。但为了区分是出错的时候返回的0，还是底数为0的时候正常运行返回的0，我们还定义了一个全局变量g_InvalidInput。当出错时，这个变量被设为true，否则为false。这样做的好处是，我们可以把返回值直接传递给其他变量，比如写double result = Power(2, 3)，也可以把函数的返回值直接传递给其他需要double型参数的函数。但缺点是这个函数的调用者有可能会忘记去检查g_InvalidInput以判断是否出错，从而留下了安全隐患。由于既有优点也有缺点，因此，我们在写代码之前要和面试官讨论采用哪种出错处理方式最合适。

此时我们已经考虑得很周详了，已经能够达到很多面试官的要求了。但是如果我们碰到的面试官是一个在效率上追求完美的人，那么他有可能会提醒我们函数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代码如下：

double PowerWithUnsignedExponent(double base, unsigned int exponent)

{

if(exponent == 0)

return 1;

if(exponent == 1)

return base;

double result = PowerWithUnsignedExponent(base, exponent >> 1);

result *= result;

if(exponent & 0x1 == 1)

result *= base;

return result;

}

最后再提醒一个细节：我们用右移运算符代替了除以2，用位与运算符代替了求余运算符（%）来判断一个数是奇数还是偶数。位运算的效率比乘除法及求余运算的效率要高很多。既然要优化代码，我们就把优化做到极致。

在面试的时候，我们可以主动提醒面试官注意代码中的两处细节（判断base是否等于0和用位运算代替乘除法及求余运算），让他知道我们对编程的细节很重视。细节很重要，因为细节决定成败，一两个好的细节说不定就能让面试官下定决心给我们Offer。

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/16_Power

测试用例：

把底数和指数分别设为正数、负数和零。

本题考点：

考查应聘者思维的全面性。这个问题本身不难，但能顺利通过的应聘者不是很多。有很多人会忽视底数为0而指数为负数时的错误处理。

对效率要求比较高的面试官还会考查应聘者快速做乘方的能力。

面试题17：打印从1到最大的n位数

题目：输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数999。

跳进面试官陷阱

这道题目看起来很简单。我们看到这个问题之后，最容易想到的办法是先求出最大的n位数，然后用一个循环从1开始逐个打印。于是我们很容易就能写出如下的代码：

void Print1ToMaxOfNDigits_1(int n)

{

int number = 1;

int i = 0;

while(i++ < n)

number *= 10;

for(i = 1; i < number; ++i)

printf("%d\t", i);

}

初看之下好像没有问题，但如果仔细分析这个问题，我们就能注意到面试官没有规定n的范围。当输入的n很大的时候，我们求最大的n位数是不是用整型（int）或者长整型（long long）都会溢出？也就是说我们需要考虑大数问题。这是面试官在这道题里设置的一个大陷阱。

在字符串上模拟数字加法的解法，绕过陷阱才能拿到Offer

经过前面的分析，我们很自然地想到解决这个问题需要表达一个大数。最常用也是最容易的方法是用字符串或者数组表达大数。接下来我们用字符串来解决大数问题。

在用字符串表示数字的时候，最直观的方法就是字符串里每个字符都是'0'～'9'之间的某一个字符，用来表示数字中的一位。因为数字最大是n位的，因此我们需要一个长度为n+1的字符串（字符串中最后一位是结束符号'\0'）。当实际数字不够n位的时候，在字符串的前半部分补0。

首先把字符串中的每一个数字都初始化为'0'，然后每一次为字符串表示的数字加1，再打印出来。因此，我们只需要做两件事：一是在字符串表达的数字上模拟加法；二是把字符串表达的数字打印出来。

基于上面的分析，我们可以写出如下代码：

void Print1ToMaxOfNDigits(int n)

{

if(n <= 0)

return;

char *number = new char[n + 1];

memset(number, '0', n);

number[n] = '\0';

while(!Increment(number))

{

PrintNumber(number);

}

delete []number;

}

在上面的代码中，函数Increment实现在表示数字的字符串number上增加1，而函数PrintNumber打印出number。这两个看似简单的函数都暗藏着小小的玄机。

我们需要知道什么时候停止在 number上增加1，即什么时候到了最大的n位数“99999”（n个9）。一个最简单的办法是在每次递增之后，都调用库函数strcmp比较表示数字的字符串number和最大的n位数“99999”，如果相等则表示已经到了最大的n位数并终止递增。虽然调用strcmp很简单，但对于长度为n的字符串，它的时间复杂度为O(n)。

我们注意到只有对“99999”加1的时候，才会在第一个字符（下标为0）的基础上产生进位，而其他所有情况都不会在第一个字符上产生进位。因此，当我们发现在加1时第一个字符产生了进位，则已经是最大的n位数，此时Increment返回true，因此函数Print1ToMaxOfNDigits中的while循环终止。如何在每一次增加1之后快速判断是不是到了最大的n位数是本题的一个小陷阱。下面是Increment函数的参考代码，它实现了用O(1)时间判断是不是已经到了最大的n位数。

bool Increment(char* number)

{

bool isOverflow = false;

int nTakeOver = 0;

int nLength = strlen(number);

for(int i = nLength - 1; i >= 0; i --)

{

int nSum = number[i] - '0' + nTakeOver;

if(i == nLength - 1)

nSum ++;

if(nSum >= 10)

{

if(i == 0)

isOverflow = true;

else

{

nSum -= 10;

nTakeOver = 1;

number[i] = '0' + nSum;

}

}

else

{

number[i] = '0' + nSum;

break;

}

}

return isOverflow;

}

接下来我们再考虑如何打印用字符串表示的数字。虽然库函数printf可以很方便地打印出一个字符串，但在本题中调用printf并不是最合适的解决方案。前面我们提到，当数字不够n位的时候，在数字的前面补0，打印的时候这些补位的0不应该打印出来。比如输入3的时候，数字98用字符串表示成“098”。如果直接打印出098，就不符合我们的阅读习惯。为此，我们定义了函数PrintNumber，在这个函数里，只有在碰到第一个非0的字符之后才开始打印，直至字符串的结尾。能不能按照我们的阅读习惯打印数字是面试官设置的另外一个小陷阱。实现代码如下：

void PrintNumber(char* number)

{

bool isBeginning0 = true;

int nLength = strlen(number);

for(int i = 0; i < nLength; ++ i)

{

if(isBeginning0 && number[i] != '0')

isBeginning0 = false;

if(!isBeginning0)

{

printf("%c", number[i]);

}

}

printf("\t");

}

把问题转换成数字排列的解法，递归让代码更简洁

上述思路虽然比较直观，但由于模拟了整数的加法，代码有点长。要在面试短短几十分钟时间里完整、正确地写出这么长的代码，对很多应聘者而言不是一件容易的事情。接下来我们换一种思路来考虑这个问题。如果我们在数字前面补0，就会发现n位所有十进制数其实就是n个从0到9的全排列。也就是说，我们把数字的每一位都从0到9排列一遍，就得到了所有的十进制数。只是在打印的时候，排在前面的0不打印出来罢了。

全排列用递归很容易表达，数字的每一位都可能是0～9中的一个数，然后设置下一位。递归结束的条件是我们已经设置了数字的最后一位。

void Print1ToMaxOfNDigits (int n)

{

if(n <= 0)

return;

char* number = new char[n + 1];

number[n] = '\0';

for(int i = 0; i < 10; ++i)

{

number[0] = i + '0';

Print1ToMaxOfNDigitsRecursively(number, n, 0);

}

delete[] number;

}

void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index)

{

if(index == length - 1)

{

PrintNumber(number);

return;

}

for(int i = 0; i < 10; ++i)

{

number[index + 1] = i + '0';

Print1ToMaxOfNDigitsRecursively(number, length, index +