小米面经~~分享出来

昨天下午去武大参加小米的笔试，一共三道题，做得很差。本以为必然没戏了，谁知道早上凌晨 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 。