一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4624|回复: 34
收起左侧

Google onsite 01/05

[复制链接] |试试Instant~ |关注本帖
lcl3356897 发表于 2016-1-19 16:37:24 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Passfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

第一轮 印度小哥
小哥在Google 8年了,太资深了.1point3acres缃
题目是,在发邮件的时候,比如输入 ben ,下边会提示名字(FirstName, LastName)或者邮件以 ben 开头的人,设计一个类来完成这个提示功能。假设每次我们返回最多10个这样的结果。. more info on 1point3acres.com
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
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. 鍥磋鎴戜滑@1point 3 acres
Follow up是,如果这些iterator都有hasPrevious(), previous()方法,意思就是后退一步,你的class也应该有这两个方法,来后退一步
比如我们现在结果返回了 1,4
这时候原来的iterator变成
i1 2, 3
i2
i3 5, 6
如果调用previous(),变成
i1 2, 3
i2 4. 1point3acres.com/bbs
i3 5, 6
. more info on 1point3acres.com
有一个情况是如果现在结果返回了 1,4,5,2
这时候原来的iterator变成
i1 2, 3
i2. from: 1point3acres.com/bbs
i3 5, 6

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

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

最后要走的时候,我问了下姐姐对previous的最优解是什么,当时可能面完太放松了。。。小姐姐说的没记住,可能的意思是对于每个iterator,我们keep track什么时候调用了这个的next,然后后撤一步。   好像不太对。。。sorry我忘了原话是什么。。。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴



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


. visit 1point3acres.com for more.

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

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

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


. Waral 鍗氬鏈夋洿澶氭枃绔,写完了之后,大哥问,最需要多少次transaction,一个人给另一个人钱的话算一次,我心想的是 O(n - 1) 就是 O(n), 大哥说specific answer, 就是 n - 1次.鏈枃鍘熷垱鑷1point3acres璁哄潧
然后Follow up,如果每次transaction特别麻烦,不管是时间还是空间都特别麻烦。如果不用考虑everything, 不考虑cpu, 不考虑硬盘,我们想让这个次数最少,怎么办。



.鏈枃鍘熷垱鑷1point3acres璁哄潧第四轮 一个亚裔,还有个白哥哥旁听
题目大概是,每次用户会调用一个方法 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的大哥。。。

祝大家好运~

. 1point 3acres 璁哄潧

-google 1point3acres

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

评分

4

查看全部评分

本帖被以下淘专辑推荐:

wtcupup 发表于 2016-1-19 20:34:59 | 显示全部楼层
第一题是用Trie嘛?
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2016-1-20 03:13:11 | 显示全部楼层
wtcupup 发表于 2016-1-19 20:34
第一题是用Trie嘛?
. from: 1point3acres.com/bbs
嗯嗯是的
. 鍥磋鎴戜滑@1point 3 acres

字数字数~~~
回复 支持 反对

使用道具 举报

geniusda 发表于 2016-1-20 08:52:02 | 显示全部楼层
谢谢!请问楼主第三题什么思路啊,算平均,然后排序,然后two pointer?

补充内容 (2016-1-20 09:08):
我是说follow up
回复 支持 反对

使用道具 举报

comicrudy 发表于 2016-1-20 10:41:22 | 显示全部楼层
恭喜lz了,顺便问一下为什么只有4轮?
回复 支持 反对

使用道具 举报

comicrudy 发表于 2016-1-20 11:02:49 | 显示全部楼层
geniusda 发表于 2016-1-20 08:52
谢谢!请问楼主第三题什么思路啊,算平均,然后排序,然后two pointer?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2016-1-20 09:08):

应该是找matchup吧,之前的solution是n-1,只有matchup能每次减1个trans,找到去掉应该就可以了。
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2016-1-21 02:31:34 | 显示全部楼层
geniusda 发表于 2016-1-20 08:52
谢谢!请问楼主第三题什么思路啊,算平均,然后排序,然后two pointer?

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

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

使用道具 举报

 楼主| lcl3356897 发表于 2016-1-21 02:32:36 | 显示全部楼层
comicrudy 发表于 2016-1-20 11:02
应该是找matchup吧,之前的solution是n-1,只有matchup能每次减1个trans,找到去掉应该就可以了。

嗯。。。我当时也这么说的,但是这个算是个Greedy,没法证明这个的正确性. from: 1point3acres.com/bbs

不过答案不重要,思考过程最重要吧
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2016-1-21 02:33:01 | 显示全部楼层
comicrudy 发表于 2016-1-20 10:41
. visit 1point3acres.com for more.恭喜lz了,顺便问一下为什么只有4轮?

谢啦谢啦. Waral 鍗氬鏈夋洿澶氭枃绔,

我是new grad, 好像都是四轮吧
回复 支持 反对

使用道具 举报

wyccx 发表于 2016-1-21 05:03:25 | 显示全部楼层
hello~LZ能分享下offer具体的package吗?
回复 支持 反对

使用道具 举报

lrn0304 发表于 2016-1-22 00:55:14 | 显示全部楼层
Iterator那道题怎么把原数据插回去?
回复 支持 反对

使用道具 举报

arokyzxc 发表于 2016-1-22 01:27:30 | 显示全部楼层
lcl3356897 发表于 2016-1-21 02:32
嗯。。。我当时也这么说的,但是这个算是个Greedy,没法证明这个的正确性

不过答案不重要,思考过程最 ...

请问这个matchup是什么样的思路?能否展开说说,谢谢
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2016-1-22 05:49:17 | 显示全部楼层
lrn0304 发表于 2016-1-22 00:55.鏈枃鍘熷垱鑷1point3acres璁哄潧
Iterator那道题怎么把原数据插回去?

唔。。。 .1point3acres缃

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

使用道具 举报

 楼主| lcl3356897 发表于 2016-1-22 05:51:27 | 显示全部楼层
arokyzxc 发表于 2016-1-22 01:27
请问这个matchup是什么样的思路?能否展开说说,谢谢

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

使用道具 举报

lrn0304 发表于 2016-1-22 05:58:42 | 显示全部楼层
lcl3356897 发表于 2016-1-22 05:49
唔。。。 . more info on 1point3acres.com

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

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

使用道具 举报

 楼主| lcl3356897 发表于 2016-1-22 07:46:21 | 显示全部楼层
lrn0304 发表于 2016-1-22 05:58
那previous不是zigzag iterator的方法吗, 怎么变成 i1的方法了? 而且就算这个计数器-1了, 已经 next() 出 ...

啊,小姐姐说的意思是,每个Iterator都有一个previous()的方法,能把next()出去的数字弄回去

然后让我实现这个Zigzag Iterator的previous()
回复 支持 反对

使用道具 举报

comicrudy 发表于 2016-1-22 07:52:15 | 显示全部楼层
lcl3356897 发表于 2016-1-21 02:33
谢啦谢啦

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

我的是5轮,不知道为什么。。不开心~~
回复 支持 反对

使用道具 举报

chenzhan171 发表于 2016-1-22 08:07:06 | 显示全部楼层
comicrudy 发表于 2016-1-22 07:52
我的是5轮,不知道为什么。。不开心~~

我是4轮,,所以你是new grad么?
回复 支持 反对

使用道具 举报

mchzh 发表于 2016-1-22 08:08:46 | 显示全部楼层
这么大的题量,这么难,能写得完吗,好烧脑啊
回复 支持 反对

使用道具 举报

 楼主| lcl3356897 发表于 2016-1-22 14:21:14 | 显示全部楼层
comicrudy 发表于 2016-1-22 07:52
我的是5轮,不知道为什么。。不开心~~
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
唔。。。new grad应该是4轮吧,你可以找HR问问

palpate

补充内容 (2016-1-22 14:21):
我想发的是  patpat...
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 01:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表