Google刚面完新鲜出炉Onsite3.9

原帖地址:一亩三分地

2015(1-3月) 码农类 硕士 全职@Google – 网上海投 – On Site |Other
第一轮,面的是白人大叔,一上来就做题,一个matrix,实现两个functions,第一个是设置某个位置的value的function,这个小学生都能做,O(1),第二个是给两个位置坐标,这两个位置坐标形成的长方形的值的和,最暴力的方法O(n^2), 大叔说这个function可以怎么优化,答可以预处理,提前算好某个位置到(0,0)形成的长方形的和,然后这样第二个function就可以O(1)实现。大叔继续follow up,那这样的话每次设置了某个位置的value后都需要update每个包含了这个值的长方形的和,所以第一个function又是O(n^2)了,能不能balance一下,后来给他讲了一种两个functions都是O(n)的方法,大概就是只提前存好一维数组的和,大叔表示满意,然后coding实现
第二轮,面的人是华裔小哥,人很喜感也挺nice,也是一上来做题。题目是给你一个positive的值K,然后按照fraction的值的小到大输出所有n/d, 其中1<=d<=k, 0<=n<=d,还有一个要求输出的fraction不能有duplicate,比如1/2和2/4是duplicate,这种情况只要输出1/2。我用了一个hashtable来处理duplicate的情况, fraction的实际小数的值对应其输出string,比如0.5对应1/2,因为输出要按从小到大顺序,所以还用了个arraylist存实际小数的值,最后对这个List排了下序,然后结合hashtable和list输出最后结果。然后问时间复杂度,follow up,如果规定只想要输出某个数值区间的fraction怎么办,数学的一些东西,算下值范围就好了,还问了这种情况的复杂度。 第三轮,面的人是白人小哥,给一个matrix,里面只有0和1,将每一个由1组成的component的indices存入一个list,然后把所有component的list又加入一个list,用了DFS另加一个visited matrix。完成代码后,小哥问了复杂度等,由于用了stack,所以size很大的时候会overflow,有什么办法优化?答BFS,小哥表示满意,这个没有让写代码。之后见时间够加了一题,给一个数字range的array和另一个range,如{[1, 4], [7, 9], [11, 14]}和[10, 13], 求合并之后的结果,{[1, 4], [7, 14]}, 小哥说只需要讲思路,然后我讲了下大概思路。 第四轮,悲剧的遇到了三哥,题目是surpass count,题目貌似是经典题,但这会lz已经精疲力尽,答得很不好,中间卡了很久,估计这轮悲剧了 写出来给自己的job hunting之路攒下RP吧,GG的话就让它随风而去吧,耳边响起let it go。。。