［转自CSDN］编程技术面试的五大要点

文 / 何海涛

扎实的基础知识、高质量的代码、清晰的思路、优化代码的能力、优秀的综合能力是编程技术面试的五大要点。

找工作一直是一个热门话题。要想找到心仪的工作，难免需要经过多轮面试。编程面试是程序员面试过程中最为重要的一个环节。如果能在编程面试的环节充 分展示自己的能力，那么拿到中意的Offer就是水到渠成的事情。

我先后在欧特克、微软和思科等公司任软件工程师，多次接受他人的面试，同时也面试过很多人。总结面试与被面试的经验，我发现尽管面试官的背景、性格 各不相同，但都关注应聘者五种素质：扎实的基础知识；能写高质量的代码；分析问题时思路清晰；能优化时间效率和空间效率；具备包括学习能力、沟通能力、发 散思维能力等在内的综合能力。

扎实的基础知识

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

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

［1. 只是大的变量不要传递值就可以，引用还是指针的问题，没有定论，只是习惯不同，有个观点不错，用指针传进来有很多是void *，用引用都不知道怎么用。

2. const & 参数，是一个常对象，而常对象只能只能访问它自己的const 成员函数，所以这对我们使用object的成员函数造成一些限制。如果不慎使用了非const成员函数，会造成编译错误。 ］

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

大部分公司对算法的要求都只是考查查找和排序。应聘者可以在了解各种查找和排序算法的基础上，重点掌握二分查找、归并排序和快速排序，因为很多面试 题都只是这些算法的变体而已。比如把排序好的数组的前面若干个数字移到数组的后面，然后问怎样在这个数组之中找到最小的数字。这道题其本质就是考查二分查找。少数对算法很重视的公司比如谷歌或者百度，还会要求应聘者熟练掌握动态规划和贪婪算法。如果对这种类型的公司感兴趣，那么应聘者在参加面试之前就应该 加强对相关算法题目的练习。

高质量的代码

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

举个很多应聘者都被问过的一个问题：写一个函数，把字符串转化成整数。这道题看似很简单，绝大部分计算机专业的毕业生都能用十行以内的代码实现最基 本的功能。可是在实际面试过程中，十个应聘者中只有一个人能通过这道题的面试，因为绝大部分应聘者不能全面考虑到各种特殊输入，比如输入的字符串含中有非 数字的符号、在字符串的开头有正负号、字符串中有正负号但其位置不是在字符串的开头。

除此之外，面试官还希望应聘者能考虑的边界条件包括2147483647（0×7FFFFFFF，int能表示的最大正整数）和 -2147483648（0×80000000，int能表示的最小负整数）。

除了边界条件和特殊输入考虑不足之外，面试官还有一个不能容忍的错误就是程序崩溃。面试时很多应聘者都会忘记对空指针做特殊处理而导致程序崩溃。如 果面试时遇到链表、二叉树相关的题目，应聘者一定要特别小心。因为这两种题目对应的代码里通常会有大量的指针操作，如果考虑不周到，就有可能对空指针进行 操作而使程序崩溃。

比如这样一道题：输入一个链表的头指针和一个无符号整数k，输出该链表的倒数第k个结点。这个题目很多人都能想到用两个指针来解决：第一个指针先在 链表上移动k-1步，同时让第一个指针和第二个指针在链表上移动。当第一个指针移动到尾指针时，第二个指针指向的就是倒数第k个结点。然而不是每个应聘者 都能根据正确思路写出完整的代码。不少应聘者会忽略两种可能：一是输入的链表头指针有可能是空指针；二是链表上结点的数目有可能少于k个。忽略这两点的代 码都存在崩溃的可能，从而很难获得面试官的青睐。

要想写出鲁棒的高质量代码，需要在动手写代码之前想好测试用例。在写代码之前，先要想好各种边界条件和特殊输入作为测试用例。当代码写好之后，自己 在心里用之前想好的测试用例来检验自己写出的代码，这样就能在面试官之前发现并解决问题。以求链表的倒数第k个结点为例，如果事先想到了输入头指针为空指 针和链表上的结点总数少于k这两个测试用例，并且在写好代码之后在心里模拟代码的运行过程，确保能够通过这两个测试用例的测试，那么这轮面试必然是能够通 过的。

清晰的思路

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

应聘者可以用几个简单的方法帮助自己形成清晰的思路。

首先是举几个简单的具体例子让自己理解问题。当一眼看不出问题中隐藏的规律时，可以试着用1~2个具体的例子模拟操作的过程，这样说不定就能通过具体的例子找到抽象的规律。

其次可以试着用图形表示抽象的数据结构。像分析与链表、二叉树相关的题目时，可以画出它们的结构图来简化题目。

最后可以试着把复杂的问题分解成若干个简单的子问题，再一一解决。很多基于递归的思路，包括分治法和动态规划法，都是把复杂的问题分解成一个或者多个简单的子问题。

比如把二叉搜索树转化排序的双向链表这个问题就很复杂。碰到这个问题，不妨先画出1~2个具体的二叉搜索树及其对应的排序双向链表，直观地感受二叉搜索树和排序的双向链表有哪些联系。如果一下子找不出转换的规律，可以把整个二叉树看出三部分：根结点、左子树和右子树。当递归地把转换左右子树这两个子 问题解决之后，再把转换左右子树得到的链表和根结点链接起来，整个问题也就解决了。

【解法：转为链表实际上就是转为中序遍历。 http://www.cnblogs.com/XjChenny/archive/2011/10/01/2197783.html】

[

1.二叉搜索树 和 二叉排序树 其实差不多

排序树狭义来说就是排个序，不考虑搜索效率问题，也就是二叉树平衡性，树可能退化成链表；
搜索树一般会要求搜索效率，平衡性是搜索效率的一个最重要指标，所以一般都要考虑平衡性；

2.

当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作；
若有序表里动态查找表，则应选择二叉排序树作为其存储结构。

]

优化代码的能力

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

要想优化时间或者空间效率，首先要知道如何分析效率。即使是同一个算法，用不同方法实现的效率可能也会大不相同，要能够分析出算法及其代码实现的效 率。例如求斐波那契数列，很多人喜欢用递归公式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)完成查找。数组的这个特征可以用来实现简单的哈希表解决很多面试题，比如在字符串中找到第一个只出现一次的字符。再比如为了找出n个数字中最小的k个数，需要一个数据容器来存储 k个数字。在这个数据容器中，我们希望能够快速地找到最大值并且能快速地替换其中的数字。经过权衡，我们发现二叉树比如最大堆或者红黑树都是实现这个数据容器的理想选择。

如果只是英文字符的话，相对距离【标杆是'a'】即可,所以用一维数组足够了
int main()
{
    char c[]="abaccdeff";
    int bit_map[26]={0};
    int i=0;
    for(;i<strlen(c);++i)
            bit_map[c[i]-'a']++;
    for(i=0;i<strlen(c);++i)
    {
        if(bit_map[c[i]-'a']==1)
        {
            printf(" %c ",c[i]);
            break;
        }
    }
    if(i>=strlen(c))
        printf("No ele to the rule\n");
    return 0;
}

从N个数中选最小的K个数：参考下面的条件1和条件2

http://blog.csdn.net/arrow_pig/article/details/6192033
条件1） 能够在O(1)时间判断一个新的数字是不是已有的K个数字中最大的

条件2 )  如果不是现有的K个数中最大的话，我希望在最短时间内，丢弃现有K个数中的最大的那个数，放入新的数，并且最适当调整，使调整后的数据结构仍然满足 条件1).
结果就是 最大堆 （Max Binary Heap）. 对于Binary Heap,每次调整，最坏情况时间复杂度是 log(k)。 前K个元素不许要调整（因为我还没有开始建立堆结构），剩下N-K个元素，最坏情况为 (N-K)log(K)。



代码：



/*
 * 题目：输入n个整数，输出其中最小的k个。
   例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。
 */

public class MinNPicker {

    private int[] m_binaryHeap;
    private int m_numberChecked; //indicate how many elements have been checked

    public MinNPicker(int size){

        m_numberChecked = 0;
        m_binaryHeap = new int[size];
    }

    public void print(){
        for(int i: m_binaryHeap){
            System.out.println(i);
        }
    }

    public void add(int[] elems){
        for(int i: elems){
            add(i);
        }
    }

    public void reset(){
        m_numberChecked = 0;

    }

    public void add(int elem){

        if(m_numberChecked < m_binaryHeap.length){
            m_binaryHeap[m_numberChecked++] = elem;

            if(m_numberChecked == m_binaryHeap.length){
                //now let's construct the binary heap
                //for a binary heap of N size, N/2 to N elements are leaf nodes(leaf nodes are already heap)

                int smallestLeaf = m_binaryHeap.length/2;

                for(int i=smallestLeaf-1; i>=0; i--){
                    maxHeapify(m_binaryHeap, i);
                }
            }
            return;
        }

        if(elem < m_binaryHeap[0]){  //0 is the root, also the max element

            m_binaryHeap[0] = elem;
            maxHeapify(m_binaryHeap,0);
        }
    }

    private void maxHeapify(int[] array, int index){
        //we use a max heap to contain only N elements, everytime we're feed a new element
        //if new elem > max elem within heap, we replace that ex-max elem and redo max-heapify

        //our internal array to hold the heap is 0-based, so left-child(i)=2i+1, right-child(i)=2i+2
        //maxHeapipy assume that both left child and right child of i are already heap

        int largest = index;

        int size  = array.length;
        int left  = index*2 + 1;
        int right = index*2 + 2;

        if(left < size && array[index] < array[left]){  //! make sure left < size, otherwise exception
            //left child is bigger
            largest = left;
        }

        //now let's compare the right child and the largest
        if(right < size && array[largest] < array[right]){
            largest = right;
        }

        //only swap when largest != index
        if(largest != index){
            int tmp = array[index];
            array[index] = array[largest];
            array[largest] = tmp;

            //because we swap the content between index and largest, it's not sure if the original
            //left child/right child tree are still hold heap property
            //!!don't forget to recursive call maxHeapify itself
            maxHeapify(array,largest);
        }


    }

    public static void main(String[] args){

        int[] givenElems = {8,7,6,5,4,3,2,1};

        MinNPicker picker = new MinNPicker(4);
        picker.add(givenElems);
        picker.print();

        System.out.println("-------");
        int[] givenElems2 = {1,2,3,4,5,6,7,8};
        picker.reset();
        picker.add(givenElems2);
        picker.print();



    }
}

要想优化代码的效率，也要熟练掌握常用的算法。面试中最常用的算法是查找和排序。如果从头到尾顺序扫描一个数组，需要O(n)时间才能完成查找操 作。但如果数组是排序的，应用二分查找算法就能把时间复杂度降低到O(logn)。排序算法除了能够给数组排序之外，还能用来解决其他问题。比如快速排序 算法中的Partition函数能够用来在n个数里查找第k大的数字，从而可以用O(n)的时间在数组中找到出现次数超过数组长度一半的数字。

【使用partition函数，将数组分为两组。partition函数是快速排序中用来把数组分成两部分的函数。
            (1)分为两个组，sa和sb。
            (2)若sa组的个数大于K，则继续在sa分组中找取最大的K个数字 。
            (3)若sa组中的数字小于K ，其个数为T，则继续在sb中找取 K-T个数字 。】

如果面试题 是一个求最大值或者最小值的题目，则可以尝试用动态规划法或者贪婪算法，比如用动态规划法求出数组中连续子数组的最大和。

优秀的综合能力

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

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

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

[台阶问题实际上就是 此数列的一种演化，考虑从n-1到n的跳跃，相对于n-1时的排列，需要加1，共有两种方式，原有基础上直接在后面加 1【f(n-1)】，最后一位也可以为2，2之前就是f(n-2)种排列。]

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

小结

我们可以用下图来总结出应聘者需要具备的素质。

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

作者何海涛，思科高级软件工程师，之前先后 任职于Autodesk和微软。主要关注C++/C#的开发技术，并对设计模式和项目管理也很感兴趣。