励志贴: 报个G家offer+面筋

原帖地址:米群网

从去年11月on campus,到圣诞前的on site,再到现在(1月)拿到offer,G家的面试贯穿了整个求职历程,报喜讯的同时顺便也把on site的面筋分享一下。

on campus面筋戳这里http://www.meetqun.com/thread-2227-1-1.html,on site有3轮,上午10点左右开始,午饭前两轮,午饭后一轮。

第一轮================================
warm up 小于5分钟,然后就开始做题,关于用树表达图像的题目。假设一个矩形画布(理解为一个区域),该区域只能由黑白两种颜色填充,然后根节点表示的就是这个矩形画布。
1. 一个节点表示图中的某一个区域,如果该区域全黑或者全白,那么它将不会有children(不会被split)。
2. 如果该节点中颜色错杂,那么把该区域平均划分成四块(左上,右上,左下,右下),这时该节点就有4个子节点。

3. 这样一直递归下去
上面就是基本的情景,然后要求写出树节点的Class表达方式,为后面问题作铺垫。

第一个问题很简单,求树的高度,用了两种方法,一是根据树递归构建的性质进行递归遍历,另一个就是层次遍历(滚动数组)来做。
第二个问题就是将两幅大小相同的图merge为一个新图,merge规则为对于两幅图上的同一个像素点,如果颜色相同,那么颜色不变,如果1黑1白,那么merge之后为白色。当然面试官是通过画了一个示例图来讲述的题目,可能会更好理解一些。我就用最容易想到的recursive的方法来做了。

第二轮================================
warm up 5~10分钟,然后就开始类似于聊天方式的做题(是个设计题),情景很长,跟gmail里显示广告有关。精练后就是有一个server,用来处理client向server发送的request请求,这个server会针对每个request返回true or false,这样得到true的client就可以向advertisement server发送获取广告的请求。这样做的目的就是限制访问,免得ad server宕机。问怎么设计这个server。。。

第三轮================================
个人觉得这一轮命悬一线,一上来就直接做题。

第一题给一个BST(树节点的索引都是不重复的),然后给一个threshhold value,该value可能出现在树中,可能没有,要求分开成两棵树,一棵节点值小于等于threshhold,另一个大于threshold。这个题关键是定义好递归方程的API(即每层递归到底要做什么),然后静下心来做。

第二题是关于二维的region merge,当然题目被封装成描绘城市轮廓。在2维平面上的一堆矩形方块,每一个方块表示一个建筑物在地平面上的横截面,默认这些建筑都在同一水平线上,所以一个方块的数据结构可以表示为Building ,即在水平线上左右轮廓的坐标和高度。现在问题来了,给你一堆的方块,这些方块可能重合,那么要求返回所有方块的整体轮廓。返回结果的数据结构需要自己定义。

总结================================
由于master才读的CS,没有任何实习经验,一直都觉得能拿到G家offer真是一种看缘分的事情,可遇不可求。。。所以面试过程中心态还算好。码代码的过程中也出现了一些bug,也有一些地方还待优化,都是面试官提醒才改过来的。所以大家不要因为在过程中出现了bug就影响情绪,个人觉得相比于bug free,过程中与面试官的交流会更加重要。然后再强调一下心态的重要性,在第三轮BST题出来的时候,我就有种“完了,好难”的感觉,因为这种树的递归题,说容易也容易,说难也难,关键是在那个时间那个地点你想明白没有,做得出来OK,做不出来也不能说明什么,真的有种看天意的感觉,所以就抱着挂掉的心里准备安安静静分析,死马当活马医。。。