12/14 Google Onsite (@Youtube San Bruno)

原帖地址:一亩三分地

过了那么多天 发个面经攒人品 周一在youtube campus面的,一共四轮:1. 中国大叔,给一个sorted array,包含数字1-N,每个数字出现3次。现在删掉里面的一个数,让你return 删掉的那个数是什么,要求log N time.
比如:1 1 1 2 2 2 3 3 4 4 4 那么return 3

这题其实不难 只要binary search,地里也都出现过。可惜楼主当时由于紧张+没想清楚,只写了大概的binary search function,里面的index那些并没有写的很清楚。建议大家看过之后都自己写一下,因为这题要把 index那些都写清楚也是挺不容易的

2. 一个白人,进来先跟我看了下简历,然后大谈c++ 和python的区别,从memeory, run time, compile/interpret, garbage collection等方面说了许多。楼主最后一次用python是很久之前了,并不清楚基本的底层,所以支支吾吾 大概都在他的提示下答出来了,尽管我多次和面试官说明了我对java 和c++更熟悉。这里建议大家要对自己简历上的内容熟悉,里面都是有可能被提问的。 然后就问了我一个binary search 的问题,说有一个class product, 一个method getCost(int quantity), 现在给你money, 问你能买最多多少个product,

本来楼主回答的是从INT_MAX往下二分,他说不能用INT_MAX,所以后来设了一个l , r 然后不断double r 来找出能买的product的上限。

3. 一个阿根廷的小哥,之前在加拿大后来调来了San Bruno,长的很帅很帅,人也很好。刚开始先问了我number of island II的问题,我想的比较快,直接说了思路,然后他说这太快了,再给我一道题,让我两道里面挑一道做。第二题是给一个的tree,让你找出里面所有的subtree pair A, B 使得 A = B 或者 A 和 B 是isomorphic 的。这题我大概和他讲了下思路,先把leaf->child标记为”#”,用一个preorder去表示一个subtree,然后就变成关于string的对比了。

感觉小哥对这轮挺满意,说了”you nailed it”,这轮我的感觉是 自己熟悉的题目不要一开始讲出答案,要一步一步来,我是做完第二题 后来挑第一题写code, 并且最后提出了union find的想法。关于第二题,我也提出了 suffix tree那些想法,让小哥觉得我对data structure 比较熟悉

4. 一个大胡子美国人,有一个shadow 在旁边学习,我一直以为大胡子是练习的。上来先说我们准备design 一个cache system, 有两个method, slowGet(string key) 和fastGet(string key),怎么样design这个cache system使得实现fastGet,楼主慢慢和他讨论 直到引出LRU Cache。

实现了 LRU 之后,大胡子开始和我讨论,如果request很多,我的方法会不会有问题。我说会,可能multi-thread会出问题,得加mutex 或者SOPhomore。之后大胡子说那如果之后系统很慢怎么办,我和他说 可以design database, 用sharding,然后问我怎么shard,我说可以根据地区,因为亚洲区的人query同样的query可能比较多。然后又问我如果这样还是很慢呢?我说可以每个地区的database 再进行load balancer分配request, 用master-slave 或者master-master去管理database server。这题讨论很多,感觉还比较顺,很面试官的交流很重要。

申明:虽然Google说new grad不需要system design,但是最后一轮无意中和大胡子这么聊下去,他还是很乐意往那方面引导的。所以其实你准备了,还是能留下好印象的。其实system design的问题大家只要花1天左右准备,就可以有很多话聊了。具体怎么准备,地里也有。

总结:感觉1,2两轮跪了,今天接到 HR 电话说送了 HC,问了下feedback是不是positive, 没听清。希望新年前可以出结果。 另外请教一下地里的小伙伴,是所有的面试都会送 HC 吗还是有选择的送 HC。