google onsite面经

原帖地址:一亩三分地

接了offer有一段时间了,然后天天吃,喝,玩,乐,颓废了一阵,今天把onsite面经写出来,给google面经题库里再加几道目前正在等选组,希望后面一切顺利
当天我的面试官好像是迟到了,和我一个building里等待的同学一个一个被叫走,就剩我一个了。后来HR过来先领我逛了一下campus,着重去了一个restroom->我是说休息室不是卫生间,让我玩了一个好像是3D的google map,重点就是强调google很cool,对员工很好,我就一路附和下去,内心OS是:能不能别讲了,我好紧张,能不能先让我去面试。。。。

下面是干货
**************************************************分割线***********************************************************

第一轮:美国大叔,一个股票的stream,每个时间点(timeline)都有股票的更新,实现两个function:1.给一个timeline,删掉当前点的股票2.给你一个timeline让你求出历史股票数据的最大值和最小值我使用heap和hashmap做的
第二轮:国人姐姐1.给一个linkedList,返回倒数第n个node,这个题我已开始竟然说先把链表反转,真想一巴掌拍死自己。。。。有时候真的紧张会大脑短路2.给一个complete tree,返回最后一个level的叶子(用二分的思路)剩下的时间讨论了下类似于unique tree的题,没写code
午饭是内推我的前辈带我去吃的,因为比较紧张,所以并没有留意是不是好吃,好像还行吧
第三轮:俄罗斯姐姐带了一个shadow白人小哥,这个小哥全程红脸,不知道是紧张还是本身就自带腮红一个matrix,里面的每一格是白色或者黑色,已知黑色的block都是conntected的,让求matrix里的黑色格子的上下左右四个边界。我当时说DFS遍历,过程中记录四个边界,她说有没有better solution,然后提示我说如果是一个一维的你会怎么做,然后我就想到了二分。。。这一轮有一个比较trick的follow up,我硬是想了快20分钟,就是在找左右边界的时候我用了两个function,面试官问我能否把这两个合成一个,然后中间提示我说这个board里面只有黑白两个颜色,让我往颜色的方面考虑,可惜直到最后我也没想出做法。。。。最后她说ok, it looks…nice….good luck…然后我觉得我一定是没戏了回家的路上想到了,其实很简单,你们先自己想想
第四轮 都是leetcode国人小哥1.string to integer2.excel sheet column title第二题我也是刷了很多遍,但是现场写居然写了好久才写出来,后面10分钟小哥让我证明为啥我的解法是正确的,可惜最后还是没能领会他的意思,但是从结果来看,这个小哥应该是帮了我一把的,很感谢*********************************************************************************************************************下面依然是水货君
1.google onsite整体感觉很好,每个面试官都很亲切,整个过程很像是你和面试官一起讨论把题目解出来的
2.拿到题目,可以先说brute force的解法,在进行优化,如果卡住了可以主动问面试官要一下hint
3.我面试的白板和我想象中的不一样,有点小,并且是高度大于宽度的,所以我总是写了擦,擦了写
4.比起bug free,面试官更看重你的思路,还有你对数据结构和算法是不是能够灵活应用
5.中国同胞出题都更加偏向leetcode,而且都很给力,你懂得
6.找工作的这段期间真的很难熬,而且愿意给我面试的公司又很少(google算是我第二个onsite),我记得拿到offer的前几天真的觉得压力好大,跟朋友打电话哭来着。。。我想每个人大概都一样吧,找到工作前都有一段苦逼成狗的岁月,所有事情都是自己一个人撑,所有情绪都是自己一个人知道,但是,请坚持,再坚持一下。。。

最后,求选组顺利啊!

补充内容 (2016-1-8 12:35):
complete tree那道题是返回最后一个level的最后一个叶子