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<Integer>>, 这个里边是iterator
i1 1, 2, 3
i2 4
i3 5, 6
然后结果返回 1,4,5,2,6,3
Follow up是，如果这

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

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

> 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前面

lrn0304 发表于 2016-1-22 00:55
Iterator那道题怎么把原数据插回去?

唔。。。

我的想法是对于每个Iterator，用一个int保存之前next出去了多少个数字，然后找到第一个比当前大的
比如现在结果返回了 1,4,5,2 那么就变成了
i1 3           2个
i2 4           1个
i3 6           1个
所以我们应该对i1调用previous，并且把这个int减去1

arokyzxc 发表于 2016-1-22 01:27
请问这个matchup是什么样的思路？能否展开说说，谢谢

我当时的思路是尽可能匹配到两个人和average的差值的一样的，比如有个人多掏了10刀，另一个人少掏了10刀。这样的话，理想状态下，最后的transaction的次数就是 n / 2， n是多少个掏钱不是avg的人(不管是多掏了还是少掏了)    但是这样没办法保证正确性

lcl3356897 发表于 2016-1-22 05:49
唔。。。

我的想法是对于每个Iterator，用一个int保存之前next出去了多少个数字，然后找到第一个比当 ...

那previous不是zigzag iterator的方法吗, 怎么变成 i1的方法了? 而且就算这个计数器-1了, 已经 next() 出去的数字也回不到 i1里面去了呀? 我想问的就是最后这个, 嗯嗯求讲解谢谢~

第一题是用Trie嘛？

wtcupup 发表于 2016-1-19 20:34
第一题是用Trie嘛？

嗯嗯是的


字数字数~~~

谢谢！请问楼主第三题什么思路啊，算平均，然后排序，然后two pointer?

补充内容 (2016-1-20 09:08):
我是说follow up

恭喜lz了，顺便问一下为什么只有4轮？

geniusda 发表于 2016-1-20 08:52
谢谢！请问楼主第三题什么思路啊，算平均，然后排序，然后two pointer?

补充内容 (2016-1-20 09:08):

应该是找matchup吧，之前的solution是n-1，只有matchup能每次减1个trans，找到去掉应该就可以了。

geniusda 发表于 2016-1-20 08:52
谢谢！请问楼主第三题什么思路啊，算平均，然后排序，然后two pointer?

补充内容 (2016-1-20 09:08):

临走时候我抓住大哥问了下，大哥说因为什么都不用考虑，就bruto force，找到所有的可能方案，然后选出最少的那个。。。。。。。。。。。。。。

comicrudy 发表于 2016-1-20 11:02
应该是找matchup吧，之前的solution是n-1，只有matchup能每次减1个trans，找到去掉应该就可以了。

嗯。。。我当时也这么说的，但是这个算是个Greedy，没法证明这个的正确性

不过答案不重要，思考过程最重要吧

comicrudy 发表于 2016-1-20 10:41
恭喜lz了，顺便问一下为什么只有4轮？

谢啦谢啦

我是new grad, 好像都是四轮吧

hello~LZ能分享下offer具体的package吗？