登录
  • #美国面经
  • #码农类general
  • #面试经验
  • #google

Google刚面完新鲜出炉Onsite3.9

autumnhu
7889
44
第一轮,面的是白人大叔,一上来就做题,一个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)的方法,大概就是只提前存好一维数组的和,大叔表示满意,然后codin

本帖隐藏的内容需要积分高于 188 才可浏览,点击前往一亩三分地论坛阅读

用了stack,所以size很大的时候会overflow,有什么办法优化?答BFS,小哥表示满意,这个没有让写代码。之后见时间够加了一题,给一个数字range的array和另一个range,如{[1, 4], [7, 9], [11, 14]}和[10, 13], 求合并之后的结果,{[1, 4], [7, 14]}, 小哥说只需要讲思路,然后我讲了下大概思路。

第四轮,悲剧的遇到了三哥,题目是surpass count,题目貌似是经典题,但这会lz已经精疲力尽,答得很不好,中间卡了很久,估计这轮悲剧了{:4_106:}

写出来给自己的job hunting之路攒下RP吧,GG的话就让它随风而去吧,耳边响起let it go。。。
44条回复
热度排序

发表回复