艺龙elong公司面试归来

今天下午去参加了下艺龙elong旅行公司的面试，一面：自我介绍完了，开始做题。先让写了个字符串翻转的代码，很快写完。然后是用非递归法对二叉树进行前序遍历，由于比较生疏了，勉勉强强写完代码，感觉写的比较乱，但是思路还是说清楚了，就是有点儿繁琐，面试官就让我做了另外一个题：在二叉树中找出所有的有两个父结点的结点，我想这已经不是树了啊，变成图了，就以图的方式想，想了一会儿，我说可以找所有有两个孩子的结点，然后看这两个孩子结点的孩子结点中是否有共同的结点。。。面试官说太烦了，找问题的实质（其实他所谓的问题实质是判断链表中是否有环，可是这其实是有向无环图啊，感觉他自己都没把问题理解清楚。。。），然后这个题就过去了（回来想想，其实无非是在有向无环图中找两条仅首位重合的路径）。接着是一个判断链表是否有环的题，说完快慢指针法，面试官就让给出另外的解法，我想到了一个O(n^2)的算法，就是记录已经遍历过的每个结点，同时每遍历一个后继查找下历史结点比较是否有已经遍历过，然后让优化，想了一会儿没想出来，面试官提示说用二分查找，但是还是没有想出来。接着问了点技术方面的，有线程同步的方法，进程间通信的方法，C++中多态的理解和实现原理，这几点还答得不错。

 

二面：一面答得马马虎虎，算是勉强进了二面。二面的面试官比较和蔼谦逊，面带微笑，自我介绍完也主要是做题，但不用写代码。第一个是给你一些包含重复项的query，找出出现次数最多的前10个不同的query，我用hash+最小heap的方法很快讲出了思路，感觉答得还行。第二个问题是一个概率的题，题意是：分别有大小相同的50个红球和50个蓝球均匀的装在同一个袋子里，然后给你两个相同的框，要求随机从袋内抓球放入两个框中，但是抓出的球你看不到，放到框内你也看不到，且最后每个框内至少要有一个球，不过放球的策略你可以自己定，把球放完，最后要求从两个框中取出一个球，取出红球的概率达到最大，给出朝框内放球的方案？感觉这个题其实只用关心最后两个框中球的分布，然后计算相应的概率最大值对应的球的个数即可，面试官听完表示理解了我的思路，但最后结果我没有算出。第三个题目是一道系统分析题，题意是这样的：有一个用户query请求处理系统，分为前端接收query层，中间的cache服务器层，后端查询层，中间和后端是负责查询的，cache的查询速度大概0.0001s，后端的查询速度大概为0.1s，系统在运行中会有两种情况出现：第一种是cache空间不够时，需要增加cache服务器；第二种是cache服务器宕机时要及时剪掉。问这两种情况发生时分别会对系统造成怎样的影响？我仅仅从系统负载均衡和命中率的角度进行了简单描述，但是没有抓住关键技术点——用户请求的query是以某种hash的方法分发到不同的cache结点上的，如果改变已有的cache结点，那么原有的hash结果就有变动，也就是说cache上query的分布发生了变化，那么再按以前的query查询方式查询cache就会出现命中率降低，造成后端查询的负载加大，这时，如何设计hash达到理想的状况——也即使得改变cache服务器后系统受到的影响最小化？这个问题我确实没有在实际中接触过，还有就是对具体的hash设计没有一个清晰的思维方式，导致答不到重点。最后还问了些项目问题和一点技术问题（指针与引用的区别），这部分答得还好。

 

二面完期待三面啊，过了一会儿，面试官过来说今天的面试就到这儿，要亲自送我回去。面试官一直面带微笑，最后我问了下是不是我不合适啊，面试官说我回答问题表达上没有抓住重点，但是我的基础挺扎实的，还有可能调到其他部门（也许吧），呵呵，这应该也是一种委婉的拒绝方式。今天面完，我感觉还是没有白跑的，跟面试官讨论技术还是蛮nice的，而且面试官最后还耐心的指出了我的问题，挺难得，这也让我在技术层面上认清了自己一些：之前互联网面试一路跪我已经习惯了，也许真的是职位不合适吧，但其实自己的真正问题还在于算法和技术功底还远远不够扎实，平时也没有用心积累，热情程度不够。选择做技术就要对自己严格要求，对技术怀有一颗热情的、执着追求和探索的心，唯有如此，才能说自己够格做技术这行。

 

最后，用“路漫漫其修远兮，吾将上下而求索”这句话来勉励下自己