Google 面试 01

今年年初的时候 申请过一次google的实习生，当时指针用的太残疾，导致一次悲剧了，这之后我练习过很多次，感觉有所提高，后来还好各大面试不是都是指针的问题，这也是我的weak point。后面面试过腾讯和微软，微软成功了，但是腾讯失败了，原因就是当时出言不逊还有和HR说了我申请微软的事情吧。

上周三，电面了Google，主要原因就是自己GCJ前1000吧，而且之前还有面试经历，这次希望会好一点。
当时面试了3个题目：1.写一个区间合并的题目，我大概写吧写吧完了。2.有25匹马，每次能5匹一起跑，选出最快的3匹最少需要几次。我当时给的答案是8次，每次5匹分5组比较，再拿出每组的第一进行一次比较，一下子删除掉后两组的5只和前三组的后两只，然后剩下的2次比较就行。回头我仔细想了想其实可以7次完成。这个就留个大家思考好了。第三题是个曼哈顿距离和最小点，最开始我就给了个模拟退火，后面面试官希望我改进一下，我当时脑袋浆糊了，没有想完，其实觉得暴力一下也可以，初始的点算完之后，后面的点可以简单的利用曼哈顿距离的性质。然后晚上接到HR的电话，他人很NICE，可能因为我之前加了他LinkedIn……和我说了很多问题，然后给我安排了现场面试。。。

这周三就是现场面试了，进去之前每次有人问我从哪里来的，我说我哈工大本科生，他们就说我碉堡了。。。我也不知道是鄙视我工还是鄙视本科。。进去之后面了3个人，从现在来看，是逐级悲剧递减的。。。第一个面试官问了我关于使用rand3()[0~2]来生成32Bit正整数的问题，顺便问了我使用rand3的次数的期望。感觉答得很顺利，然后问我了一个被我简化后就是一个判是否存在欧拉回路的问题，然后我记得判度数忘了判联通被提醒一下后写了个DFS就结束了。第二个人问我的一些2分啊 分治啊 最后问我面向对象的东西，最后他还是觉得我本科生能有这样表现很厉害。。。第三个人就是上来一段英文，我有点怯场，然后问我如何操作使得维护一个机器的集合：1.插入id 2.删除id 3.随机找到id（要求每个集合内部被找到的概率均等）,我开始给了一个vector,只是因为随口说的，后来考虑到了复杂度就改成平衡树了，我说了三个操作的复杂度，分别是logn,logn,o(n)，然后他说想让我用vector,然后我就改用vector之后用的map,这里他觉得map用的不错，然后不拉不拉，就到时间了，感觉最后一个面试官时间卡的特别紧（39分钟）,他是北大的本科生，然后去美帝读书之后又在google总部工作了4年。

这次面试发现了很多有意思的事情分享一些：1.google的人喜欢用mac的特别多。。。2.google大部分项目是用c++完成的。。3.google秉承的原则是宁缺毋滥，所以他的职位也身价倍增。有的时候我觉得度娘招人招的太多了，导致现在less top级别的人不是很想去了。话说我当初的目标很简单，能去一个和百度差不多的公司就很高兴，现在却没有兴趣了，有时候真的觉得面试就是一个2分的过程，这次遇到了一个上界，也许过一段时间我可以把它变成下界，总之人生有想法是最好的事情。

晚上就收到了hr电话，说我的问题是没有亮点，也没有弱点，确实说的很中肯。大学期间总是按照周围人的级别来衡量自己，最后regional也只是拿个银牌草草了事，就像当年我做化学竞赛和数学竞赛的时候一样，以为只要在周围人中算是佼佼者就行了，周围的人不够强确实是个很大的问题，但是我每次都喜欢给自己留了太多的空间确实我一直无法面对的问题。总之我还需要很长的路去走。