Google onsite 01/05

原帖地址:一亩三分地

刚收到hr的邮件,说offer approved了
先来发面经

第一轮 印度小哥
小哥在Google 8年了,太资深了
题目是,在发邮件的时候,比如输入 ben ,下边会提示名字(FirstName, LastName)或者邮件以 ben 开头的人,设计一个类来完成这个提示功能。假设每次我们返回最多10个这样的结果。

Follow up I,如果希望返回的结果是alphabetic有序的,比如输入ben的时候, benaa 在 benbd 前面,怎么设计。
Follow up II,如果我们希望FN是ben开头的在LN是ben开头的前边,比如 ben Back 在 ben Smith前面怎么办。

第二轮 可能是个国人姐姐 姐姐用的英文名字。。。
国人姐姐从进门就笑呵呵的,自然就放松好多
开始的题目是LeetCode的Zigzag Iterator
比如我们有一个 Iterator>, 这个里边是iterator
i1 1, 2, 3
i2 4
i3 5, 6
然后结果返回 1,4,5,2,6,3
Follow up是,如果这些iterator都有hasPrevious(), previous()方法,意思就是后退一步,你的class也应该有这两个方法,来后退一步
比如我们现在结果返回了 1,4
这时候原来的iterator变成
i1 2, 3
i2
i3 5, 6
如果调用previous(),变成
i1 2, 3
i2 4
i3 5, 6

有一个情况是如果现在结果返回了 1,4,5,2
这时候原来的iterator变成
i1 2, 3
i2
i3 5, 6

那么调用previous的时候怎么知道调用 i1.previous() 还是 i2.previous()

最后姐姐跟我大概讨论了下concurrent怎么办
用个lock,或者用sigleton pattern,对这个synconize 这个 instance

最后要走的时候,我问了下姐姐对previous的最优解是什么,当时可能面完太放松了。。。小姐姐说的没记住,可能的意思是对于每个iterator,我们keep track什么时候调用了这个的next,然后后撤一步。 好像不太对。。。sorry我忘了原话是什么。。。

午饭 一个国人小哥
紧张的没吃多少,估计小哥也没吃太饱吧。。。好对不起他。。。qucik吃完之后,小哥说如果你想的话带你看看campus,大概转了一圈,太大了。。。

第三轮 国人大哥
大哥也不能算高冷,就是特别严肃
上来先warm up了下,如果我们要在internet传输数据的话,我们要compress和encrypt数据。我们应该先compress还是先encrypt

我什么都不知道。。。我就瞎说了下,然后大哥说,看起来你真的是know nothing about this… 我就傻了。。。。

大哥说,没事,这就是个warm up, 来继续战斗,来个算法题吧
如果你和另外两个朋友出去玩,每个人付一部分钱,比如你掏了car rent, 另一个人付了hotel等等。最后回家了,你们想AA,最后你们每个人付的钱都一样,写个方法能返回谁应该给谁多少钱
比如三个人分别掏了5,3,1,那么a[2]应该给a[0] 2 刀
如果现在有n个人的话,应该怎么办

写完了之后,大哥问,最需要多少次transaction,一个人给另一个人钱的话算一次,我心想的是 O(n – 1) 就是 O(n), 大哥说specific answer, 就是 n – 1次
然后Follow up,如果每次transaction特别麻烦,不管是时间还是空间都特别麻烦。如果不用考虑everything, 不考虑cpu, 不考虑硬盘,我们想让这个次数最少,怎么办。

第四轮 一个亚裔,还有个白哥哥旁听
题目大概是,每次用户会调用一个方法 double next(double v) 然后函数返回的是这个数之前的 windowSize个数的average
比如windowSize是3,call了 next(10) next(11) next(3) call(1), 第一个返回 10, 第二个返回 10.5, 第三个返回 8, 第四个返回 5
. 涓憨-涓夊垎-鍦帮紝鐙鍙戝竷
因为我用了Deque来保存之前的数据,我以为他会问精度的问题,我记得面经里有人发过,结果没问。。。所以Follow up 是 如果不用现成的Deque这个class,你怎么办。 好像用个链表更好写。。。我作死说可以用一个rotated array来模拟这个功能,其实也挺简单

Time Line 大概是1.5面 —> 1.7告诉我feedback收集完了但是没告诉我具体怎么样 —>1.11告诉我review team 给了 green light, 应该就是过了hc吧—> 1.19告诉我svp同意了(因为1.19是MLK day,hr姐姐16号请假出去了,要不然按原计划她说可能16号就能给我结果)

找工作真的好煎熬,尤其是身边都是大神,我身边有早早拿到return的大哥,有各种Onsite拿到手软的满GPA大哥,还有早早拿到我dream company的大哥。。。

祝大家好运~

补充内容 (2016-1-20 03:15):
第一轮的follow up II的例子给的不太对,应该是 ben Black 在 mike Bend前面