在面试中，很多算法设计问题都是各家企业历年来的现成题目，不管求职者以前对算法知识学习得是否扎实，理解得是否深入，学上一段时间，牢记于心，应付此类题目应该没有问题，但遗憾的是，很多世界级知名企业也深知这一点，如果纯粹是出一些毫无技术含量的题目，会让考前“突击手”占尽便宜，这样不利于人才的选拔，所以，为了把优秀的求职者与一般的求职者能够更好地区分开来，他们往往会推陈出新，越来越倾向于出一些有技术含量的新题。
在面试中，算法的地位如同托福考试在出国考试中的地位——是必需的但不是最重要的，它只是众多考核方面中的一个，不直接决定求职者的“生死”。虽然如此，但并不是说不用去准备算法知识，因为算法知识回答得好，必然会成为面试的加分项，对于求职成功，百利而无一害。那么，如何应对此类题目呢？很显然，编者不可能将此类题目都在《程序员面试笔试宝典》中一一解答，一来由于内容众多，篇幅有限；二来也没必要，今年考过了，以后一般就不会再考了，不然还是没有区分度。编者以为，靠死记硬背肯定是行不通的，解答此类算法设计问题，需要求职者具有扎实的基本功以及良好的运用能力，这里仅提供一些比较好的答题方法和解题思路，以供求职者在面试时应对此类算法设计问题。
（1）归纳法 此方法通过写出问题的一些特例来分析总结其中的一般规律。具体而言，就是通过列举少量的特殊情况，经过分析，最后找出其中的一般关系。例如，某人有一对兔子饲养在围墙中，如果它们每个月生一对兔子，且新生的兔子在第二个月后也是每个月生一对兔子，问：一年后围墙中共有多少对兔子？
使用归纳法解答此题，首先想到的就是第一个月有多少对兔子。第一个月，最初的一对兔子生下一对兔子，此时围墙内共有两对兔子。第二个月仍是最初的一对兔子生下一对兔子，共有3对兔子。到第三个月，除最初的兔子新生一对兔子外，第一个月生的兔子也开始生兔子，因此共有5对兔子。通过举例，可以看出，从第二个月开始，每一个月兔子总数都是前两个月兔子总数之和，Un+1=Un+Un-1，一年后，围墙中的兔子总数为377对。
此种方法比较抽象，也不可能对所有的情况进行列举，所以，得出的结论只是一种猜测，还需要进一步证明。
（2）相似法 如果面试官提出的问题与求职者以前用某个算法解决过的问题相似，此时就可以触类旁通，尝试改进原有算法来解决这个新问题。而通常情况下，此种方法都会比较有效。
例如，实现字符串的逆序打印，也许求职者从来就没遇到过此问题，但将字符串逆序肯定是在求职准备的过程中见过的。将字符串逆序的算法稍加处理，即可实现字符串的逆序打印。
（3）简化法 使用此方法，应先将问题简单化，例如改变一下数据类型、空间大小等，然后尝试着将简化后的问题解决，一旦有了一个算法或思路可以解决这个被简化过的问题，再将问题还原，尝试用此类方法解决原有问题。
例如，在海量日志数据中提取出某日访问×××网站次数最多的IP。很显然，由于数据量巨大，直接进行排序不可行，但如果数据规模不大，采用直接排序不失为一种好的解决方法。那么，如何将问题规模缩小呢？于是想到了散列法，散列往往可以缩小问题规模，然后在简化过的数据里面使用常规排序算法即可找出此问题的答案。
（4）递归法 为了降低问题的复杂度，很多时候都会将问题逐层分解，最后分解为一些最简单的问题，这就是递归。使用此种方法，应先解决最基本的情况，然后以此为基础，解决其他问题。(www.xing528.com)
例如，在寻求全排列时，可能会感觉无从下手，但仔细推敲，会发现后一种排列组合往往是在前一种排列组合的基础上进行重新排列，一旦知道了前一种排列组合的各类组合情况，只需要把最后一个元素插入到前面各种组合的排列里面，就解决了这一问题，即先截去字符串s[1，…，n]中的最后一个字母，生成所有s[1，…，n-1]的全排列，然后再将最后一个字母插入到每一个可插入的位置。
（5）分治法 任何一个可以用计算机求解问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。而分治法也是如此，即将一个难以直接解决的大问题，分割成一些规模较小的相同问题，各个击破，分而治之。分治法一般包含三个步骤：①将问题的实例划分为几个较小的实例，最好具有相等的规模；②对这些较小的实例求解，而最常见的方法一般是递归；③如果有必要，则合并这些较小问题的解，以得到原始问题的解。
分治法是程序员面试常考的算法之一，一般适用于二分查找、大整数相乘、求最大子数组和、找出伪币、金块问题、矩阵乘法、残缺棋盘、归并排序、快速排序、距离最近的点对、导线与开关等。
（6）散列法 很多面试笔试题目都要求求职者给出的算法尽可能高效。那么，究竟什么样的算法是高效的？一般而言，时间复杂度越低，算法越高效。而要想达到时间复杂度的高效，很多时候就必须在空间上有所牺牲，即“用空间来换时间”。而用空间换时间最有效的方式就是散列法、大数组、位图法。当然，此类方法并非“包治百病”，有时面试官也会对空间大小进行限制，此时，求职者只能再去思考其他的方法了。
其实，凡是涉及大规模数据处理的算法设计，散列法就是最好的方法之一。
（7）轮询法 每道面试笔试题，在设计时，往往会有一个载体，这个载体便是数据结构，例如数组、链表、二叉树、图等。当载体确定后，可用的算法自然而然地就会显露出来。可问题是，很多时候并不确定这个载体是什么。当无法确定这个载体时，求职者一般也就很难想到合适的方法了。
编者建议，此时求职者可以采用最原始的方法——轮询，在脑海中轮询各种可能的数据结构与算法，从中找出一种合适的解法。常考的数据结构与算法知识点见下表。
此种方法看似笨拙，其实很实用，只要求职者对常见的数据结构与算法烂熟于心。
为了更好地理解这些方法，求职者可以在平时的准备过程中，应用此类方法去答题，练习得多了，自然就熟能生巧了，面试时遇到此类问题，也就能够应对自如了。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
