小米面经-2014

    昨天下午去武大参加小米的笔试，一共三道题，做得很差。本以为必然没戏了，谁知道早上凌晨1点半来了面试的短信通知。招聘人员真的是辛苦了。

    今天下午一点半，在武汉珞珈山国际大酒店进行面试，题目记录如下：

1.两个已序数组A,B,将两个数组进行归并，并将结果存放在数组B中，B足够大。例如A={1,3,5},B={2,3,5},结果B={1,2,3,4,5,6}

    答：这一题比较简单。关键在于从尾向头进行赋值，否则可能会覆盖需要的值。代码如下（未调试过）

void func(int *A,int lenA,int *B,int lenB)
{
    int m=lenA-1;
    int n=lenB-1;
    for(int i=lenA+lenB-1;i>=0;)
    {
        if(m==0)
        {
            break;
        }
        else if(n==0)
        {
            for(;m>=0;m--)
            {
                B[i]=A[m];
                i++;
            }
        }
        else
        {
            if(A[m]>=B[n])
            {
                B[i]=A[m];
                m--;
                i++;
            }
            else
            {
                B[i]=B[n];
                n--;
                i++;
            }
        }
    }
}

2.改进昨天笔试中的一道题目：两个数组I1,I2,二者只有一个公共子序列，求之。

    答：一般求最大公共子序列的方法是动态规划，时间复杂度O(mn)（我昨天笔试就是这么做的，结果只得了12分，满分20）。但是这一题说明了只有一个公共子序列，因此不必那么麻烦，只要找出I2中也属于I1的元素就行了。

这一题我首先想到的是bitmap，因为查找速度很快O(1),但是空间复杂度较高，面试官让我想想能不能把空间复杂度降低，我想到了hashtable.

    首先将I1里的数全部存入hashtable,然后遍历I2,只要该数在hashtable中，证明它是公共子序列中的元素，直接打印出来。这样时间复杂度就是O(n)了。

代码我就不贴了，比较简单。建议大家也看看bitmap，在处理大数据的搜索时，很有用。

3.为什么Linux分为内核态和用户进程态？什么时候这二者会进行切换？

    答：这题完全不会，只有硬着头皮答了。在用户进程调用系统函数时，会进入内核态。其他就不知道了。

后来面试官给我讲了讲这一题：之所以分开，是因为内核态可以操作更多的硬件资源，而且不用用户去关心，如果让用户自己操作，可能会产生许多错误。用户态切内核态有三种情况：1.系统调用，2.异常，3.外围设备中断。感觉这题和底层硬件关系密切。

一面结束，紧接着是二面。

二面的问题乍看之下都很难，但是自己思考其实也没那么难，我是在面试官的提醒下才答出来的。感觉不怎么好。

1.一个数组中有100w个整数，这些整数的范围时1~99999，要求打印出重复的数字。

    答：最先想到的还是bitmap，但是空间复杂度太高。面试官说改进一下，想破头没想出来。最后请求面试官能否告知答案，结果十分之巧妙，估计我自己再多想几个小时也未必想得出。

    解法如下：

    这100w个数据存在一个数组里，每一个数可以让他对应一个位，这叫位图。举例来说，假设第一个数是59，我就让他对应59位，第二个数是63，我就让他对应63位。如果有重复数字，那么也就是说有多个数对应相同的一位。我们在遍历的时候，对位做一个记号，如果碰到有的位已经被记号过了，那证明之前已经有过这个数了。

具体来说：假设这个数组是A={59,63,46,.....59,.....}，第一个数是59，我们就让A[59]=A[59]-1000000,这样A[59]就小于0了，这就是标记。当遍历到第二个59时，我们会再去检查A[59],发现A[59]已经小于0了，因此前面肯定一应有了一个59，使A[59]减了1000000，当遍历到A[59]时，我们去找A[A[59]+1000000]。不知道这么解释清楚没有。

2.在一定精度内求根号n，n>=1。

    答：一接到这一题，我蒙了。记得以前好像做过这题，我没搞出来，好像方法很复杂，一下没了信心。面试官提示了我一下，可以用二分法，我一下豁然开朗。

其实就是一个二分查找。代码如下（没测试过）：

float n;
float e;//精度
 
float func(float beg,float end)
{
    float f = (beg+end)/2;
    float f2 = f*f;
    if(f2-n<=e && f2-n>=-e)
    {
        return f;
    }
    else if(f2-n>e)
    {
        return func(beg,f);
    }
    else
    {
        return func(f,end);
    }
}

3.N个木头和N个石头，木头之间质量两两不同，石头也是。但是木头的质量和石头的质量一一对应，现在给你一个天平，将木头和石头分成质量一一对应。

    答:这一题我都没直接答出来。瞎了。其实很多题目，当你知道答案以后，觉得很简单。因此理解答案对我们来说并不困难，只是我们没有一个很好地方法将思路引向答案。这也与平时我们所受到的教育有关，我们从小到大，受到的都是欧几里得式的教育。即先给出结论，再证明之。我们从来没有去探究怎么想到这个结论的。更详细的内容我推荐大家看看一本书，叫做《暗时间》。

    回到这一题，相信大家已经有答案了。最笨的方法当然是一一对比，时间复杂度为O(n^2),有没有更快的呢？首先，比O(n^2)快一个数量级的时间复杂度是O(nlgn),这不正是比较类排序的下限吗？给了个天平，正好用于比较。因此，我们用时间复杂度为O(nlgn)的排序方式（快排，归并，堆排等）将两堆分别排序即可，排序后就一一对应了。

    至此，面试结束。

    总结一下。感觉小米对算法和思路的要求比较高。我投的是路由器软件研发，居然没有问我TCP/IP的知识。小米的编程语言大部分是Java,但是面试的时候，也没涉及过编程语言的问题。互联网公司对编程语言问题问得一向很少。其实关键在思路，有了思路，用什么语言实现并没很大差。所以完全没必要去纠结什么学C++还是JAVA。