我的阿里巴巴校园招聘面试

到了面试的那天,上午吃过早饭后十点打车去学校附近的地铁站,然后转乘地铁到了北京南站,乘坐京津城际铁路C2211次列车,开始了面试的旅程。

我去阿里巴巴面试其实是有几分意外,在线笔试开始的前一天才开始看阿里巴巴的消息,看完后立刻投简历,第二天有惊无险地通过了阿里巴巴研发方向的在线笔试。预约面试的时间也差点打乱了去哈尔滨参加物理学年会的行程安排。不过还好北京的面试场次在预约系统开放一个小时之后就全部被约满了。每个session足有45分钟,但面试只有两天,想想可能是北京通过笔试的人比预计的要多吧,所以这么快就约不上了。几分钟后再去预约页面就自动跳转到天津的场次了,无奈只好预约了天津的面试。万幸的是,天津的面试时间比北京晚了几天,这样就不会打乱之前的行程了。

十一点半出天津站后乘公交车去面试的酒店。上车后想起来为什么之前没有查询地铁线路呢?乘公交是会晕车的。不过还好路程并不算太长,在快要坚持不住的时候就到站了。

到了酒店,大厅里就摆着阿里巴巴的面试引导牌,同时还有其他几家公司也在这里面试。

到了阿里巴巴的场地,只见过道里摆着一张长桌,几个工作人员好像在整理文件,时不时地在电脑上输入些什么。见我来了,其中一人介绍说这里是面试的签到处,研发职位需要选择C++还是Java方向。虽然学习算法的时候用的是Sedgewick的那本用Java示范的Algorithms,但其实我一句Java也没写过,用的是C和C++(写了两套,C style and C++ with template),所以想都不用想必须要选C++方向。之后交上简历就出去吃饭了。

吃完饭回来后,回到候面厅,小憩了一会。下午两点多清醒过来之后,发现前面的座位上有一个头上有很多白头发的人,好像是研究生,从他和旁边同学的交谈中得知,他是今天上午来霸王面的,而且通过了三轮面试,接下来要和阿里巴巴的工作人员谈一些其他的事情了。这时我有点感觉不妙,三轮面试?那预约系统里显示的就只是第一轮面试的时间了,我还根据那个结束时间早早买好了回去的车票。想到这里,我立即起身,到服务台询问。工作人员说,整个面试可能会持续到晚上九十点,现在整体面试进度已经有点延后了,所以可能要等很久。然后我告诉她,我是从北京过来面试的,回去的车票已经买好了,希望能早点面完。旁边的工作人员人也凑过来对她说,那就提前安排一下吧。只见她看了看面试安排,过了一会儿说,四点的已经排好了,不能加进去了,就帮忙安排到三点吧。于是我在道谢后回到了候面室等待。还专心地看了一轮之前投影仪上一直在循环播放的阿里巴巴宣传片。期间工作人员时不时过来带人去面试,也有时候只是说,“X,你今天的面试结束了,可以回去等通知了。”

果然还没到三点,就有人来带我去见面试官了。面试是在旁边的一个房间里进行的,一个房间里散布着五六个面试官,每个人面前一张小桌子,上面放着笔记本电脑,还有纸和笔。简单的寒暄和自我介绍之后,就开始了第一轮技术面试。

一开始面试官好像没有打算细看简历,就让我简要介绍一下,然后问到了在学校的某个科研项目。我先是讲了讲两次神经元网络仿真的经历,一次是重复别人的,另一次是建立自己的。重点突出从第一次网络仿真中得到的某些经验教训对第二次网络仿真的帮助。期间面试官又问搞神经网络的为什么不去面试大数据职位,之前某同学也问过我类似的问题,于是我就又解释了一遍我们的目的是研究神经生理等方面疾病,而别人的神经网络是用来搞人工智能的。之后又问了些模型搭建的细节,不知道我讲清楚了没有,不过感觉她也没想深究。

然后她看到我简历上有做LeetCode Online Judge的答题代码链接,就问我的答题通过率是多少。我是不记得这些的,不过当时带了笔记本,如果能上网的话,我就能把这些东西展示出来。但是很可惜,她没有让我连网的意思。她想了想说,找不到个人页面就没办法看到通过率了,于是改问我自己感觉做的怎么样。我说,那段时间刚学完算法(Dasgupta,Papadimitriou,和Vazirani的那本Algorithms),拿LeetCode练练手,用上C++的STL里的containers和algorithms,可以很精炼地写出解答。

这时候面试官说,用STL的话可能会有些问题,比如用<vector>的话,即使把vector清空了,内存也不会释放。我心想,这东西我很熟悉的,看Bjarne Stroustrup的那本The C++ Programming Language (4th Edition) 的时候,书中在实现<string>的时候就有这种设计,<vector>也是类似的。于是马上接话,讲了讲<vector>的简单实现,还有capacity和size。

然后他又问我平时运行程序的时候,有没有观察到变量在析构之后,程序占用的内存并不会减少。我心想,这东西我看书的时候倒是见过,STL里面很多container都有allocator这样一个模板参数,默认的那个allocator可能会产生她所说的那种效果。之后她又补充道,这也不是内存泄漏,知道是为什么吗?于是我就开始解释,STL用的allocator在获取了析构释放的内存后,可能并不会立即交给操作系统,而是放在自己维护的一个memory pool里。所以就看不到内存释放,想立即释放用自定义的allocator就行了。然后她又接着问allocator和memory pool,我说只用过默认的,不了解内部的机制,真担心接下去就要问这种设计的优缺点和内存分配与回收的几种方法。她也就没有再追问。

然后她又问,在使用STL的时候遇到过什么错误吗?我心想,好像还真没遇到过什么STL的错误,只是有一次在LeetCode上解Max Points on a Line的时候,调用<map>花了点功夫。我于是说,有一次用<map>的时候,自定义了一个class,没有定义比较大小的那个函数(数学上叫order),结果发现不能用,然后自定义了一个比较大小的函数,就用上了<map>。

然后就问到了<map>,这个东西在我看的那本算法书上叫symbol table,我还用C语言实现过一遍半残的版本(找第k个最小节点有性能问题)。我就说STL里的<map>是用红黑树实现的。她就让我讲讲红黑树,那我就按算法书上讲的,从2-3树讲到红黑树,讲了讲相对平衡的原因,还有查找的复杂度,平均log n,worst case 2*log n,也不知道讲清楚了没有,因为没什么反馈。期间她说我讲的2-3树是B树,我说它是B树的一个特例,她又让我讲讲B树,我虽然可以猜到B树是什么,但是没有看过细节,就说了不了解,然后又回到了红黑树。实际上并没有讲完,比如left leaning实现,插入后的善后操作。不过感觉她不是特别关注这些,因为缺少反馈。

接着她又问红黑树的插入操作复杂度是多少。我想了想,说log n。她又问为什么,我说,找到插入的正确位置复杂度是log n,插入的过程可以在constant time完成。

然后她又问知不知道<set>,我说就是<map>去掉value。然后她问为什么不用<vector>而用<map>。又问到我熟悉的了,其实算法书上讲了symbol table的array实现,还和其他实现比较了一下。我说,因为<vector>是线性存储,插入操作很花时间(专业的说法是复杂度高),<set>用红黑树实现插入就会快一些。

接下来,她就开始问她所关注的问题了,不过那时我还以为在继续考察我对STL的熟悉程度。

接着她提出了一个新的问题,有一个消息队列,一方面有新消息产生会放入队列,另一方面需要取出消息进行处理,如何实现?我心想,怎么难度一下子降低了?算法书上的queue和priority queue比map要简单多了。不过我还是说,用queue或者priority queue,priority queue用heap实现。这时她问为什么要用priority queue呢?我说因为优先级高的消息要优先处理。她说就写个队列吧,线性结构的就行,不用priority queue,put()和get()会同时调用。我说,这可能要用到锁,但是我不太熟悉操作系统API,可以写伪代码吗?她立即说可以。这时我心想,终于图穷匕见了,淘宝每年双十一都是高并发,之前笔试题也有一道关于促销抢购的设计,现在面试里的多线程设计也来了。这东西我是必然写不对的,不过我还是在纸上写了个支持single producer和single consumer的<queue>,模仿STL的设计,用了template<class MSG>,RAII,连变量名都是仿Bjarne Stroustrup书里的代码,队列容量不够的时候,capacity自动翻倍。估计这应该给面试官留下了好印象吧。

然后她看着我写完的代码,一边看一边猜每一句的作用,我在一旁时不时地补充几句。一上来就问为什么要传结构体进put()?为什么不用指针?我说,MSG是一个模板参数,也可以是一个指针。接着又问了问如何写引用传递,我说加and符号,接着她又问有什么区别?我就讲了讲copy和reference。接着又问了为什么用size_t,我解释它是非负的而且很长,可能是unsigned long。很快代码看完了,没什么大问题,但是她说这不是线程安全的。比如有4个worker同时在读消息,你加的锁在这里就不起作用。我只好说只考虑了单个producer和单个consumer的这种多线程。之后在她的指导下,写出了一个支持高并发的<queue>。

然后她问,现在有一个线程放消息进队列,4个worker线程取消息进行处理,如何实现?我说用一个共享内存区域进行通讯,4个worker等待共享内存的通知。她又问如果只想通知其中一个worker呢?我说用不同的共享内存进行单独的通讯。这时她又详细解释道,比如只想通知一个空闲的worker,其他的继续sleep或干别的事。如何实现?我说这需要调用操作系统API,我不是很了解。

然后她说,虽然你的队列满了之后会自动扩容,每次变原来的2倍,但如果内存不够了怎么办?我问,是无法申请到连续的存储区域了吗?她说是的。我说可以用矩阵来存,矩阵行内是连续的内存,行间不需要是连续的。她又说数据量太大,内存不够怎么办?我说使用external storage。可惜上一句是我在出来之后想到的,当时我的回答是那处理不了了就throw exception吧。她笑着说那程序不就崩溃了,信息也丢了。

之后进入下一个领域,说说宏和inline的区别。我说macro效果是有保证的,一定会实施,inline的话只是向编译器发出申请,不一定会通过。之后又问了些什么。我说macro在编译预处理阶段就展开了,之后就不存在了,inline的话要在之后才会被处理。接着她又问我编译的过程。我说先是编译预处理,把那些macros全展开,然后编译每个translation unit,最后link起来。问为什么要link?我说因为有相互调用。

然后她又问熟悉Linux环境吗?还是只在Windows下编程?我说很少在Linux下编程,不过在Windows下使用gcc和g++。然后她问如何查找一个lib里的函数的位置?反正我是没懂要找什么,就直接说了不知道。

接下来她又问了解网络吗?我说知道一点点。然后让我描述TCP三次握手。我就想起了一个段子,IM上发消息先问“在吗?”是有道理的,这和TCP三次握手一样,甲:“在吗?”乙:“在。你还在吗?”甲:“我还在。”于是我就开始解释,发起者发出第一个包要求synchronization,回复者发第二个包表示acknowledged和要求synchronization表示这是在回应,之后发起者回复acknowledged,建立起连接。

然后就让我描述ping过程中包传输过程,各个层次。我说,首先发起者生成ping的IP包,然后封装之后交给路由器,路由器解码之后把IP包传到Internet上,到达对方路由器后,路由器再封装IP包,然后交给目标,目标拿到之后解码然后反应。

她又问平时是否见看过IP包传输经过了哪些节点?我问,traceroute?她接着说,有时候看traceroute会发现发到某个地方就断了,全是星,可能是什么原因?我说可能是路由表出错。等了一会儿,她接着说,还有其他的原因吗?我说可能是网络拥挤这些包就被丢掉了。她又问还有其他原因吗?我说还有物理原因。她说比如?我说,地震。她微微一笑,就直接问下一个问题了。如果这些包遇到了防火墙会怎么样?我说不太清楚,心想原来是想问防火墙。

她说,知道iptables吗?我心想,这东西是以前Linux下防火墙的标准配置,不过我现在已经不直接用iptables了,openSUSE下用的是SUSE Firewall,CentOS里用的是firewalld。不过前几天有人问起iptables的配置,我还去看了一下openSUSE上的结果,发现里面有一大堆规则。然后我说,我知道iptables,不过不直接用,而是用高级的防火墙程序间接调用iptables。她问iptables能做什么呢?一边回忆我那份默认的iptables规则一边说,开放端口,屏蔽IP,限制访问速率,NAT,IP转发。期间我还听到旁边的面试官和应聘者好像是在聊前端的东西,感觉问的就简单多了。

接下来她问知道数据库吗?这个问题比较纠结,数据库课我是上过的,当时是会用,一些数据库里会用到的算法我也知道,但是现在全都不记得了。于是我只好说忘了。她问知道事物吗?我说不知道。她说,那就应该是一点也不了解数据库了。

然后她说,最后做个算法题吧,然后就把题目写给我然后讲解了一下,就出去了一趟。看到题目的第一眼,我就知道有log n的解法,因为这就是LeetCode上的那道Median of Two Sorted Arrays,但是那种解法我实在是想不起来了。不过还好我简历上写的示例代码只是部分LeetCode解答,她可能会认为这道题我以前没做过吧。在她回来之后,我说不要求性能的话我可以写一个O(n)的。然后就讲了讲怎么写O(n)的算法。然后她又问如果这是链表呢?我心想这下O(n)应该是最优的了吧,然后就讲了讲怎么写,她指出有一个小问题,我检验了一下发现确实,然后改了一下就是正确的算法了。

面试过程中,她有时候会快速地敲击键盘,好像是在填表格。

期间还问了malloc的问题,不记得怎么聊到这儿的了,我复习The C Programming Language的时候把calloc和malloc弄混了,一个有内存区域初始化,一个没有。但是我想不起来了,虽然自己偶尔用用malloc和new都有初始化,但是面试的时候说错了。

最后就是按惯例问有什么想问面试官的吗?然后就又聊了一会儿。

最后出来发现整个过程持续了一个多小时。

等待了一段时间,就到了终面,技术Leader和HR一起上。这个就不说了,我到现在也搞不清楚是个什么套路,对方说的话亦真亦假。不过在这一面得知了前面的面试官对我的评价挺好。

这一面可能也有一个小时左右吧,面完后我问可以走了吗?对方说可以了,流程都走完了。于是简单道别之后就去赶火车了。

我走出酒店之后发现外面大雨倾盆,因为有Cortana的提醒,所以来之前我是带了雨伞的。打开手机上的音乐播放器,点乱序播放,出来的是Is It Over Now? Is it over now? 我也不知道,第一次来企业面试,很多事情完全没经验。不过有时候又想,自然地去展现就好,不必刻意为了得到而去表现自己不具备的特质。面试的过程中应聘者也会在与面试官的互动中对公司有新的认识,其实可以看作是一个双向选择的过程,这样想来,结束也并不一定就是坏事。

雨中找路花了点时间,在检票前五分钟到了检票口。坐上了返回北京的C2244次列车。

4 thoughts on “我的阿里巴巴校园招聘面试

  1. logicmd

    生产者消费者模型就是考并发的啊,一般满了空了都是block住啊,怎么去扩容呢
    DB那个问的是事务,就是recovery和ACID的问题

    Reply
    1. MiffyLiye Post author

      当初考虑过AI和psychology,然后就不小心入了生物坑(computational neuroscience)。

      因为以前写的普通队列是带有capacity自动翻倍的性质,所以面试的时候就直接拿来用了。
      DB那个后来查了下,事物的英文是transaction,如果当初知道是问transaction的话说不定能答上来点什么。

      应聘的时候发现百度在重点发展deep learning,阿里也在重点宣传big data。
      要去和阿汤哥一起改变世界了。

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *