很多读者可能都知道“各个击破”的军事思想，这种思想的精髓是当敌我实力悬殊时，我们可以把强大的敌人分割开来，然后集中优势兵力打败被分割开来的小部分敌人。要一下子战胜总体很强大的敌人很困难，但战胜小股敌人就容易多了。同样，在面试中，当我们遇到复杂的大问题的时候，如果能够先把大问题分解成若干个简单的小问题，然后再逐个解决这些小问题，则可能也会容易很多。 我们可以按照解决问题的步骤来分解复杂问题，每一步解决一个小问题。比如在面试题35“复杂链表的复制”中，我们将复杂链表复制的过程分解成3个步骤。在写代码的时候我们为每一步定义一个函数，这样每个函数完成一个功能，整个过程的逻辑也就非常清晰明...

和上一节画图的方法一样，我们也可以借助举例模拟的方法来思考分析复杂的问题。当一眼看不出问题中隐藏的规律的时候，我们可以试着用一两个具体的例子模拟操作的过程，这样说不定就能通过具体的例子找到抽象的规律。比如面试题31“栈的压入、弹出序列”，很多人不能立即找到栈的压入和弹出规律。这时我们可以仔细分析一两个序列，一步一步模拟压入、弹出的操作，并从中总结出隐含的规律。面试题33“二叉搜索树的后序遍历序列”也类似，我们同样可以通过一两个具体的序列找到后序遍历的规律。 具体的例子也可以帮助我们向面试官解释算法思路。算法通常是很抽象的，用语言不容易表述得很清楚，我们可以考虑举一两个具体的例子，...

画图是在面试过程中应聘者用来帮助自己分析、推理的常用手段。很多面试题很抽象，不容易找到解决办法。这时不妨画出一些与题目相关的图形，借以辅助自己观察和思考。图形能使抽象的问题具体化、形象化，应聘者说不定通过几幅图形就能找到规律，从而找到问题的解决方案。 有不少与数据结构相关的问题，比如二叉树、二维数组、链表等问题，都可以采用画图的方法来分析。很多时候空想未必能想明白题目中隐含的规律和特点，随手画几幅图却能让我们轻易地找到窍门。比如在面试题27“二叉树的镜像”中，我们画几幅二叉树的图就能发现，求树的镜像的过程其实就是在遍历树的同时交换非叶节点的左、右子节点。在面试题29“顺时针打印矩...

“编码前讲自己的思路是一个考查指标。一个合格的应聘者应该在他做事之前明白自己要做的事情究竟是什么，以及该怎么做。一开始就编码的人员，除非后面表现得非常优秀，否则很容易通不过。”——殷焰（支付宝，高级安全测试工程师）“让应聘者给我讲具体的问题分析过程，经常会要求他证明。”——张晓禹（百度，技术经理）“我个人比较倾向于让应聘者在写代码之前解释他的思路。应聘者如果没有想清楚就动手，则本身就不是太好。应聘者可以采用举例子、画图等多种方式，解释清楚问题本身和问题解决方案是关键。”——何幸杰（SAP，高级工程师）“对于比较复杂的算法和设计，一般来讲最好在开始写代码之前讲清楚思路和设计。”——尧敏（淘宝，资...

4.1 面试官谈面试思路4.2 画图让抽象问题形象化面试题27：二叉树的镜像面试题28：对称的二叉树面试题29：顺时针打印矩阵4.3 举例让抽象问题形象化面试题30：包含min函数的栈面试题31：栈的压入、弹出序列面试题32：从上到下打印二叉树面试题33：二叉搜索树的后序遍历序列面试题34：二叉树中和为某一值的路径4.4 分解让复杂问题简单化面试题35：复杂链表的复制面试题36：二叉搜索树与双向链表面试题37：序列化二叉树面试题38：字符串的排列4.5 本章小结

本章从规范性、完整性和鲁棒性3个方面介绍了如何在面试时写出高质量的代码，如图3.16所示。 大多数面试都要求应聘者在白纸或者白板上写代码。应聘者在编码的时候要注意规范性，尽量清晰地书写每个字母，通过缩进和对齐括号让代码布局合理，同时合理命名代码中的变量和函数。 最好在编码之前全面考虑所有可能的输入，确保写出的代码在完成了基本功能之外，还考虑了边界条件，并做好了错误处理。只有全面考虑到这3个方面的代码才是完整的代码。 另外，要确保自己写出的程序不会轻易崩溃。平时在写代码的时候，应聘者最好养成防御性编程的习惯，在函数入口判断输入是否有效，并对各种无效输入做好相应的处理。图3.16...

鲁棒是英文Robust的音译，有时也翻译成健壮性。所谓的鲁棒性是指程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理。 容错性是鲁棒性的一个重要体现。不鲁棒的软件在发生异常事件的时候，比如用户输入错误的用户名、试图打开的文件不存在或者网络不能连接，就会出现不可预见的诡异行为，或者干脆整个软件崩溃。这样的软件对于用户而言，不亚于一场灾难。 由于鲁棒性对软件开发非常重要，所以面试官在招聘的时候对应聘者写出的代码是否鲁棒也非常关注。提高代码的鲁棒性的有效途径是进行防御性编程。防御性编程是一种编程习惯，是指预见在什么地方可能会出现问题，并为这些可能出现的问...

在面试过程中，面试官会非常关注应聘者考虑问题是否周全。面试官通过检查代码是否完整来考查应聘者的思维是否全面。通常面试官会检查应聘者的代码是否完成了基本功能、输入边界值是否能得到正确的输出、是否对各种不合规范的非法输入做出了合理的错误处理。1．从3个方面确保代码的完整性 应聘者在写代码之前，首先要把可能的输入都想清楚，从而避免在程序中出现各种各样的质量漏洞。也就是说，在编码之前要考虑单元测试。如果能够设计全面的单元测试用例并在代码中体现出来，那么写出的代码自然也就是完整正确的了。通常我们可以从功能测试、边界测试和负面测试3个方面设计测试用例，以确保代码的完整性，如图3.2所示。图3...

面试官是根据应聘者写出的代码来决定是否录用他的。如果应聘者代码写得不够规范，影响面试官阅读代码的兴致，那么面试官就会默默地减去几分。如图3.1所示，书写、布局和命名都决定着代码的规范性。图3.1  影响代码规范性的因素：书写、布局和命名 首先，规范的代码书写清晰。绝大部分面试都是要求应聘者在白纸或者白板上书写。由于现代人已经习惯了敲键盘打字，手写变得越来越不习惯，因此写出来的字潦草难辨。虽然应聘者没有必要为了面试特意去练字，但在面试过程中减慢写字的速度，尽量把每个字母写清楚还是很有必要的。不用担心没有时间去写代码，通常编程面试的代码量都不会超过50行，书写不用花多少时间，关键是...

“一般会考查应聘人员对代码的容错处理能力，对一些特别的输入会询问应聘人员是否考虑、如何处理。不能容忍代码只是针对一种假想的‘正常值’进行处理，不考虑异常状况，也不考虑资源的回收等问题。”——殷焰（支付宝，高级安全测试工程师）“如果是因为粗心犯错，则可以原谅，因为毕竟面试的时候会紧张；不能容忍的是，该掌握的知识点却没有掌握，而且提醒了还不知道。比如下面的：double d1, d2;…if (d1==d2)  …”——马凌洲（Autodesk，软件开发经理） “最不能容忍功能错误，忽略边界情况。”——尹彦（英特尔，软件工程师）“如果一个程序员连变量、函数命名都毫无章...

3.1 面试官谈代码质量3.2 代码的规范性3.3 代码的完整性 面试题16：数值的整数次方 面试题17：打印从1到最大的n位数 面试题18：删除链表的节点 面试题19：正则表达式匹配 面试题20：表示数值的字符串 面试题21：调整数组顺序使奇数位于偶数前面3.4 代码的鲁棒性 面试题22：链表中倒数第k个节点 面试题23：链表中环的入口节点 面试题24：反转链表 面试题25：合并两个排序的链表 面试题26：树的子结构3.5 本章小结

本章着重介绍了应聘者在面试之前应该认真准备的基础知识。为了应对编程面试，应聘者需要在编程语言、数据结构和算法3个方面做好准备。 面试官通常采用概念题、代码分析题及编程题这3种常见题型来考查应聘者对某一编程语言的掌握程度。本章的2.2节讨论了C++/C#语言这3种题型的常见面试题。 数据结构题目一直是面试官考查的重点。数组和字符串是两种最基本的数据结构。链表应该是面试题中使用频率最高的一种数据结构。如果面试官想加大面试的难度，那么他很有可能会选用与树（尤其是二叉树）相关的面试题。由于栈与递归调用密切相关，队列在图（包括树）的宽度优先遍历中需要用到，因此应聘者也需要掌握这两种数据结构。...

和数据结构一样，考查算法的面试题也备受面试官的青睐。有很多算法都可以用递归和循环两种不同的方式实现。通常基于递归的实现方法代码会比较简洁，但性能不如基于循环的实现方法。在面试的时候，我们可以根据题目的特点，甚至可以和面试官讨论选择合适的方法编程。 通常排序和查找是面试时考查算法的重点。在准备面试的时候，我们应该重点掌握二分查找、归并排序和快速排序，做到能随时正确、完整地写出它们的代码。 如果面试题要求在二维数组（可能具体表现为迷宫或者棋盘等）上搜索路径，那么我们可以尝试用回溯法。通常回溯法很适合用递归的代码实现。只有当面试官限定不可以用递归实现的时候，我们再考虑用栈...

数据结构一直是技术面试的重点，大多数面试题都是围绕着数组、字符串、链表、树、栈及队列这几种常见的数据结构展开的，因此每一个应聘者都要熟练掌握这几种数据结构。 数组和字符串是两种最基本的数据结构，它们用连续内存分别存储数字和字符。链表和树是面试中出现频率最高的数据结构。由于操作链表和树需要操作大量的指针，应聘者在解决相关问题的时候一定要留意代码的鲁棒性，否则容易出现程序崩溃的问题。栈是一个与递归紧密相关的数据结构，同样队列也与广度优先遍历算法紧密相关，深刻理解这两种数据结构能帮助我们解决很多算法问题。2.3.1 数组 数组可以说是最简单的一种数据结构，它占据一块连续...