谷歌西雅图昂塞

罕见的暴雪给我碰上了，recruiter早上还打电话来说想要reschedle,老子可是飞了半个地球来的当然没有怂, taxi说要最少等俩小时，最后花了一百刀才叫到Uber, highway上基本没有车, 谷歌campus基本也没啥人，各位面试官都是拼了命的来公司面试我，感激, 估计面试我的人都很不开心吧，perfect weather to work from home都因为我来到了公司

面试官貌似全都是google cloud的

第一轮

白人小哥

说有一个game 比如说over watch, 会capture 30s snapshot of the best play at the end of the game. 然后叫我设计一个input data structure可以提供足够的资料来支持我们的算法，然后通过process这些data来找到 Play Of The Game (POTG), 最后要返回 [playerName, time, score].

POTG 是根据玩家在30s的时间段内得分最多的玩家, 会有很多玩家，每个玩家都有自己的data list

一开始就是brute force拉，每个玩家 每秒都算一下30秒内的分数，然后保存最高的分数，时间，和分数，然后跟其他玩家比

Follow up: What if we change the POTG time to k second instead of 30s

这样time complexity 就变成了O(N * K) instead of O(N * 30s)

然后讨论了怎么优化，我就说用prefix sum array, 每个玩家只要loop一次就可以了

每一tick是1/60秒, 最后算了一下一共要花掉大概1mb内存

白人小哥最后还跟我拉扯了一下一个数据库的操作和原理, 不记得叫啥了，反正就是连接前端的数据库.

第二轮

一个很帅冷静的白人大哥，一上来就在黑板上开始画问我懂crone job不

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

的路上一开始写错了一点，面试官也反复的重复了好几遍才写对, 主要是一开始没能理解题的意思

Design a callback function to return a function on call to determine whether or not to execute a function inside the callback function, 很绕是不是

Follow up: Limit the number of call per second  from the last call

Follow up: Limit the number of call per second

最后都写出来了

总体来说，我还是比较幸运的，每个面试官人都很好，可能因为每轮只有45分钟，题目都不是很难，也有可能大过年的面试官都手下留情了吧，也不知道过了没过，祈祷

大家觉得咋样，希望渺茫不？

哈哈哈哈哈哈… 这么大的雪都不让别人wfh。你说呢？渺茫不渺茫？奸笑…

杨超越 发表于 2019-2-9 11:40
恩恩 的确 如果没有的话 你那个pq的解法是最好的
我也是各种跪面试。。。一起加油 T^T

加油哈

leixiang5 发表于 2019-2-8 01:17
哈哈哈哈哈哈… 这么大的雪都不让别人wfh。你说呢？渺茫不渺茫？奸笑…

凉了 凉了

分享的很详细，祝好运！

已加米

请问2个问题
1） 第二轮不太理解为什么需要heap呀？看起来用linkedlist和一个id到linkedlist nodes的hashmap就可以所有operation都可以O(1)呀？
2） 请问推箱子那题 另一个解法是什么呀？

谢谢

哈哈哈只想知道lz从哪里飞来的这么拼！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

albeehere 发表于 2019-2-8 07:45
哈哈哈只想知道lz从哪里飞来的这么拼！

北极附近来的, 这点小破雪算啥

楼主好人，祝有大offer!
问一下第二轮，为啥不能用set(BST) 代替priority queue? 用priority queue是因为jobs按时间先后排序，set也可以排序啊，而且查找删除也是log(n), 还可以调用标准库不用自己写heap

悲剧了，三轮可以，两个不好，说是borderline coding not up the bar