冬季实习面试记（二）

实习面试还在继续。。。

前言

上一篇文章介绍了面试爱奇艺视频搜索部、VMware驱动测试组、搜狗营销事业部的实习生的情况。回到学校后还在继续投简历，一共投了三个。一个是在北邮人论坛上看见的微软的内推，不管靠不靠谱还是投了；一个是北邮人论坛上找到的百度LBS部门的开发实习生；一个是百度音乐的实习生。

个人最倾向百度音乐的实习生，一方面自己比较喜欢音乐，另一方面这个部门的开源做的比较好，并且也有校友在里面。但是距离上次发布招实习生信息已经过去了将近一个月的时间，所以不确定是否仍在招。

到最后只有百度LBS来了面试的通知，于是风尘仆仆的去面试了。和上次去面试不同，这次面试不是纯粹的裸面了，在火车上花了两个小时的时间看了几章《剑指offer》，虽然不能提高基础能力，但对于面试还是很有帮助的。

面试地点是在奎科科技大厦，下午两点，一个面试官领我进茶水间休息室然后就开始面试了。面试的过程中还有一个团队在讨论问题，声音比较大，或多或少影响了我的思路。好吧，一个实习生的面试还想有什么样的待遇呢。

第一轮面试

介绍自己做的一个项目。我介绍的还是分布式图片缓存系统。还是从宏观上讲了下这个项目的作用，然后讲了下这个项目的架构，尤其是数据的存取过程。这个面试官看起来比较较真，当我提到了图片缓存机制的时候，他就围绕这一点使劲的问，因为图片换粗，我们用的开源的软件MemCached，他就问了如果内存不够的话怎么办，具体的算法是什么样的等等。所以，对项目的每一点需要非常熟悉，否则有可能死的很难看。
面试官拿出事先准备好的一道题目。这道题目是给出一段程序让查看有什么问题。这个程序的主体是一个函数，函数的功能很明显是将字符串转化成int型。眼熟吗？这个程序我在搜狗面试的时候写过，太幸运了，当时写的时候考虑的比较多，和面试官的讨论过程中他也给过我一些思路，所以对程序挑错很容易。我就尽量的将发现的错误都说出来，应该比较全吧。比如：宏定义不标准；没有考虑传入的NULL指针；没有考虑正负号；没有考虑非法字符；没有检查是值是否越界，即字符串表示的值是否超过最大的边界。然后他又问了怎样判断是否越界。将公式表示为 value = 10 * value + number 只需要比较 (Max – number)/10与value的大小即可。
编程题。题目也是实现准备好的，实现删掉链表中的值等于某个target的节点，返回头结点。基本需要考虑三方面：传入地址是否为空；节点连续（1个或多个）出现链表头；节点出现在链表中间。这道题写的比较好，异常情况考虑比较全面，写完后给面试官看没有问题就继续问下一个问题了。
算法题。有一个int型数组，数组的值是递增的，找出数组中下标等于数组值的那个数，这样的情况只出现过一次。这道题也算是经典题了，各种面试书里都会介绍，以前看到过，但是算法记不太清了。显然第一种方法是遍历，需要用O(n)时间。这种方法肯定不能让面试官满意的。因为这个数组是递增的，所以有了二分的思路。即，对start…end数组，判断(start+end)/2位置下标与值之间的关系分以下三种情况：
if value == (start+end)/2
if value > (start + end)/2 则一定出现在start…(start+end)/2-1中
if value < (start + end)/2 则一定出现在(start+end)/2+1…end中

利用二分法时间复杂度O(logn)，但是这个解法是不适用于有重复的数组的。说到这，当我问面试官的有没有重复的数时，他以为是否有重复不影响算法，直到我给他讲，他才明白原来是有影响的。

第二轮面试

这一轮面试面的不好，面试官气场很足，看起来很牛逼。

上来之后问搜索引擎这个项目。我负责爬虫部分，他就问了关于爬虫的东西。比如爬虫的分布式机制、URL判重方法等等。还有建立索引的方法、存储机制、使用机制、查找排名机制。这个面试官关于搜索引擎的问题问的比较深，我基本上全都答不上来或者回答的明显不让他满意。到最后实在没办法了，我跟他说这个我们的一个大作业，他就完全明白了，然后就不再刁难我了。好囧啊，这是目前为止最尴尬的面试了，两个人完全不再一个level上，没法聊啊。。。
然后就上面搜索引擎问了个分词的东西算法。例如字符串”abcde”，可以分成”a”, “b”, “c”, “d”, “e”，也可以分成”ab”, “c”, “d”, “e”，…。每一个子串对应一个得分（可以看做由概率算得的得分），设计一个算法，求出最高得分对应的分词组合。这个问题其实就是一个字符串的划分问题，划分的原则是划分到一组的子串必须是连续的。我一开始的思路是用递归的方式，但是问题解决的不够好，后来面试官提示每个字符间有隔开或者不隔开两种选择。然后考虑可以循环2^(n-1)次方，每次循环对应一个数，对这个用二进制表示，每一位为1代表隔开，为0代表不隔开。这样就可以算出每次组合的得分，并且记录组合方式了。可能面试官对这个解法比较喜欢，这个问题折腾了不少时间，还好他比较耐心。
有两张图，这两张图大部分都是一样的，需要设计一个作弊器求出两张图不一样的地方，并且每一处不一样的地方用不同的颜色标识出来。很明显，图可以用二维数组来表示，二维数组的值表示为该位置的像素值，通过比较两个数组的相同位置的值就可以知道像素是否相等。两层循环，分别从左向右和从上到下循环查看是否相同。如果不同，则以此位置为开始用广度（深度）优先的方式向右和向后递归的查找连续不同的像素点，直到没有连续的像素点。

体会

面试指导书应付面试确实有一定的作用，用来突击非常合适。
写代码时需要考虑各种异常情况的处理
第一面面试表现的比较好，第二面面的很差。。。搜索引擎问题问题基本上不会，求字符串组合方式做的比较拖沓。
这次的面试官毫不吝啬时间，给我足够的时间考虑。我也毫不客气，他不问我答案我就一直在想有没有更好的算法。
面试完了之后对结果不抱特别乐观态度，虽然第一面基本没瑕疵，但是第二面表现实在很挫。不过过了几天，HR来消息通知面试通过了。好吧，松了一口气。百度LBS部门导航组。

This work is licensed under a CC A-S 4.0 International License.