投简历

我因为是做虚拟化的，所以找了个最接近的云计算平台开发工程师投了。我是找的内推，不过流程上和直接投官方的邮箱感觉没啥区别。第二天就收到了面试通知。

面试由于目前在实习期间，基本上就是裸上，而且长期没刷题，所以算法和数据结构也基本上忘的差不多了…

一面

早上一来就开始面试，也有点没睡醒.. 先是闲聊让氛围轻松一些。之后就开始问Hadoop和Spark是否了解, 异同。这里也不怕大家看到，我只是了解MapReduce和RDD这两篇Paper… RDD还是在面试前一天晚上又重新简单复习了一下就上了, 所以只能答出来Paper里有的基本概念。这个只能说很一般吧，基本上被问了10min就摸清底了，说实话这里还是很重视技术的，学一个东西就学透彻，只是看一些网上的二手资料或者Paper啥的基本上一被问就暴露了。

之后让用非递归方式实现二叉树的先序遍历，这个我在大三的考试题做过..现场直接写的时候直接懵逼…尴尬了十几分钟，被评价不熟悉程序.. 没有复习的亏，也没啥办法。递归首先要想到栈，因为实际的递归函数调用函数也是借助栈来实现的，这里每次pop(root)然后push(right), push(left), 重复这个步骤，先序其实很简单，pop的时候输出就完了；后序的话是要保存值最后输出的；中序的话下面伪代码大致看下好了.

while (p)  
    {  
        while (p)  
        {  
            push(p);  
            p = p->left;  
        }  

        /* Left is none */
        p = pop();  
        output(p->value);  
        /* Enter right, continue */
        p = p->right;
    }

然后一道设计题，(0 ~ 10¹⁰)的范围内取100,000个数，进行去重复和排序。

这道题其实猛地一看可能是排序，实际上是个统计出否出现的问题。所以我当时第一反应就是bitmap, 因为bitmap是表示一个东西出现或没出现过最简单的表示；
接下来自然就很想到平时我们用的是一个有10¹⁰个bits的map, 这样只要知道他们是否出现过扫一遍bitmap输出为1的就自然是排好序的数字了，而且自带去重;
由于这样会用很多空间，所以我继续提出使用Hashmap, 不过面试官指出hash的话不能保证有序，所以放弃。
继续想到数据库里面列存储的提出，列存储是因为许多entry的某一列的值都一样(比如座机这一项，基本上所有的员工都是None, 只有少部分是有座机的，所以按列存可以节省很大空间).从这得到启发，我提出将范围进行分区间，因为100,000相比较10¹⁰小很多，所以大部分bitmap的值是0，那么前面的一个bit就可以表示一个范围…如果是1，那么这个范围就有数被选中，如果是0这个范围就没有。
接下来就会想到二分，此时为了涵盖0~10¹⁰, 用40个bit(2⁴⁰ > 10¹⁰)个bit就能表示一个数具体出现的位置。比如我们从0-7里面选了个4, 就可以用100，其中第一个bit表明数字是 7~4，第二个bit表示是 5~4, 第三个表示是4.. 最后一个数刚好二进制表示就是我们所需
那么根据二进制表示构造一个二叉树，一条到叶子节点的路径就能表示这个数本身，一个叶子就能明确表示一个数是否出现过，最后对这个树进行一次遍历就能输出排好序并去重后的结果了。也可以像B+树一样把所有leaf串起来..
这样一个树所有数字都在叶子且高度相同(一定为40), 由于插入新叶子是常数级，所以最终只需要O(n)就能完成所有数字的去重和排序，而且空间开销只要500KB…(面试限制是500MB)

这道题可能设计的思维过程被认可了吧，之后面试官问有没有其他优化方案。我首先回答增加cache命中率，第二个是并发执行.. 好叭这个其实是瞎扯..不过也是第一反应就说出来了囧..

二面

二面依旧是技术面，大概30min让我讲我之前做的东西，就是让我给他讲懂虚拟化..这个比较简单，毕竟在实验室也给新来的讲过，所以没什么问题。有兴趣的看我之前的Blog有讲~

然后就是让写一个atoi的函数. 之后让写测试这个函数的输入, 没什么太难的地方.. 不过这道题虽然简单但是是可以考察多非常多内容的，这个也是后来才知道的，在程序员的那些事这个公共号里面发现的。我当时答的其实属于比较一般的了，我强调了平常开发的顺序是1. 保证功能正常执行 2. 错误处理 3. 安全方面的考虑。实际开发时安全方面的考虑由于会影响到设计，是需要提前就考虑的。

这里也是强调一下，一个比较合格的答案应该是怎样的:

可用

写出的代码必须是能运行的，如果写出来的语法错误或者逻辑错误…那么只能说明没什么编码水平
健壮

健壮意味着代码拥有边界检查、能进行一定的容错，包括空参数等等
可靠

这里可靠意味着程序需要有肯定的返回值，比如出错时返回错误码等等。强语言一般都有返回值，而弱语言如果有确定返回值的话那么这个程序是可靠的。
宽容

宽容意味着能够尽可能容纳客户的各种输入，比如用户输入的是浮点数3.00001或者2.99999 我们的程序是可以将其作为整数3来进行处理的，以及是否支持超过INT_MAX的整形转换。
时延

这部分就涉及到用户体验了，当程序在长时间处理时，能否定期返回某个结果或保证处理结果在一定时间内一定有个状态的回复等等，否则当程序执行非常长的输入时，我们无法知道程序是出错还是正常运行。

我当时实现实际上是和libc中的atoi一样，没有进行什么检查，好在我提到了这些所以可能面试官也对我宽容了一些吧。

三面

三面是Boss面，创始人之一过来面我，主要是让聊我的择业想法，对星环的看法，对行业的看法，我目前的状况，星环自身的状况，他们组的介绍等等；基本上就是一个相互了解的过程，当时都快1点了…

HR面

最后HR回来聊关于自身状况、实习等等的事情，HR面基本纯闲聊了，如果有问题也可以随时提，所以没什么好说的。

Extra面

一个多月后的今天突然又收到了面试电话，了解了下好像是因为做的东西比较底层，其他组都不怎么想要的样子.. (也可能是我之前的面试答的不好，其他组看不上我…)安慰我说之前的面试是统一面，今天是分组面..

首先是一道有向连通图，带正权重的最短路径算法，不过要记录最短路径的长度，Dijkstra最短路径算法，不过在更新点的时候要记录最短路径的长度。后面又加上如果要求最短路径本身怎么做，我答的是每个点记录更新自己的父节点，然后逆推就行，面试官好像不是很满意，问我有没有不用记录的方案，没答上来..

后面问了一个项目中收获最大的一次经历，或收获最大的点。回答了一个调了2个多星期的bug, 有关页表管理部分struct类型数据对齐的内容。

最后问了我一下自己见到过的比较漂亮的代码，哪里我觉得漂亮。回答的是kernel里面使用goto进行错误处理的例子。

结果也不太清楚到底怎么样…突然加个面试还是慌得要死。

总结

星环是个挺看重技术的地方，而且对于我这种之前做系统的感觉还挺有兴趣的，里面的人非常好，工作环境非常不错！上班时间很自由不打卡，我师兄早上10点之后到，晚上20:00左右走，也不强制周末加班，可能也是因为熬过了初期创业的艰辛，到了C轮也有上百个客户，感觉也是在慢慢变得更加规范。也是拿到了Offer，面我的Boss人非常Nice，也很健谈。

整个面试过程比我想象的要长，而且面试官也都很专业，不会故意为难，也不会问那些无聊的大概、过于基础的东西，会给你充足的时间展示自己的优势，所以不用担心自己学的和他们做的好像不符等等~