一亩三分地论坛

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

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

G onsite 面经 求team match

[复制链接] |试试Instant~ |关注本帖
will_ym 发表于 2015-11-21 11:03:39 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
两周之前面的,上周五过了HC,这周executive team审批的时候结果是需要先match team,然后再决定。G是我的dream company,如果版上哪位大神能出手相助,可以站内信我,我把简历发给你,感激不尽!

店面是申请实习的时候面的,那个时候很晚了,所以木有match上host,这次直接onsite.鏈枃鍘熷垱鑷1point3acres璁哄潧
题目我尽量回忆
1. skip Iterator 和zigzag iterator for n collections。做好LC就好了。
2. 就是一个二维数组代表每个点的海拔,然后每天都下一次雨,下雨之后整个水位会长1,从0开始,然后你坐在船上从左上角出发,只有当雨水高度大于周围海拔高度的时候,你可以漂到周围那个点。问最少用几天可以到达右下角
开始地形是. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
1 2
3 4. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
然后
第一天过后雨水高度是
1 1
1 1. Waral 鍗氬鏈夋洿澶氭枃绔,
第二天过后是. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2 2
2 2
。。。以此类推。面试官说你先给一个能work的代码就行。楼主就DFS,然后面试官说给复杂度,楼主给了,面试官说优化,楼主说了DP,给了复杂度。面试官很开心。
3. 第三个题真的特别特别长,不过核心就是fisher-yates random那个算法。面试官自己都说这个题真的很长,而且不容易懂,但是他希望能写完代码。楼主就弄懂之后就开始狂写。写完之后说这个题其实你有个地方应该clarify一下,不过没什么大关系。
4. 简单说就是摩斯码。真心记不太清了。刚吃完饭,面试官很好说热身一下,先给个单词,然后给每个字母的摩斯码,然后产生出来这个单词的摩斯码。然后反过来,给个摩斯码,同样给出每个字母所对应的摩斯码,给出所有可能得单词。刷好LC就行了。有个很像的题。然后注意分析复杂度。

题目不难,我也尽力了。希望这次能match上加入dream company。

评分

6

查看全部评分

本帖被以下淘专辑推荐:

aiwojiujiu 发表于 2016-1-14 20:49:36 | 显示全部楼层
第二轮,这个题目翻译过来就是找从起点到终点的所有路径中,找一条路径,这个路径需要满足的条件是路径上的高度的最大值在所有路经中最小。
而这条最优路径上的最大值,就是所需要的积累雨水的高度。
题目其实是 trapping rain water II 的简化版,解法是用min heap。
先将起始点加入堆,然后每次pop出来的点的周围四个点再加入堆。每次pop出来的都是围墙的堆低处直到pop出来的点是终点为止。用一个变量记录pop出来值的最大值,就是我们要找的雨水高度。
最终时间复杂度是 m*n log (m*n) 因为最坏情况就是把所有点都放入heap。
trapping rain water II 不同点在于,需要计算每个点积累多少雨水,所以需要对每个点进行如上操作,不过依然可以通过dp优化到m*n log (m*n)的复杂度。
回复 支持 3 反对 1

使用道具 举报

 楼主| will_ym 发表于 2015-11-23 21:13:36 | 显示全部楼层
1 2 3 4 5 6 7 -> 1 3 5 7
回复 支持 0 反对 1

使用道具 举报

stevencsp 发表于 2015-11-21 11:44:03 | 显示全部楼层
楼主是在哪天面的?哪个office面的?
回复 支持 反对

使用道具 举报

 楼主| will_ym 发表于 2015-11-21 11:47:17 | 显示全部楼层
stevencsp 发表于 2015-11-21 11:44
楼主是在哪天面的?哪个office面的?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
3号MTV。。。。。。。
回复 支持 反对

使用道具 举报

stevencsp 发表于 2015-11-21 11:50:40 | 显示全部楼层
MTV都是周五HC吗?
回复 支持 反对

使用道具 举报

 楼主| will_ym 发表于 2015-11-21 11:52:04 | 显示全部楼层
stevencsp 发表于 2015-11-21 11:50
MTV都是周五HC吗?

这个不知道哈 我主要是一周之后发了一封邮件问了update 然后recruiter告诉我的
回复 支持 反对

使用道具 举报

stevencsp 发表于 2015-11-21 11:53:20 | 显示全部楼层
recruiter都不是主动联系你的吗?
回复 支持 反对

使用道具 举报

 楼主| will_ym 发表于 2015-11-21 11:54:20 | 显示全部楼层
stevencsp 发表于 2015-11-21 11:53
recruiter都不是主动联系你的吗?

我都是每周问一下。。。可能每个recruiter风格不同吧
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-21 11:57:59 | 显示全部楼层
请问第二题可以漂向周围是指上下左右4个点吗?DP做法是什么呢?
回复 支持 反对

使用道具 举报

 楼主| will_ym 发表于 2015-11-21 12:04:51 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-21 11:57
请问第二题可以漂向周围是指上下左右4个点吗?DP做法是什么呢?

是的啊 用一个变量代表目前雨水高度 然后用一个二维数组代表这个地方能不能到达,然后就可以更新下一时刻能够到达的点了。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-21 12:15:45 | 显示全部楼层
谢谢回复,我的理解是这样的,一个点能否在这一时刻到达有两个条件:1.周围有在之前能够到达点 2.当前雨水高度大于这个点的海拔
请问每次怎么更新看当前时刻有哪些点能否到达,是每次都遍历一遍这个二维数组吗?还是把之前可以到达的点存到一个queue里?

顺便bless lz能够顺利的team match!!!. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-21 15:22:10 | 显示全部楼层
恭喜楼主。第四题跟哪个LC比较像?
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-11-21 15:40:16 | 显示全部楼层
同问第四题 感谢楼主
回复 支持 反对

使用道具 举报

sjtucissy 发表于 2015-11-21 21:45:09 | 显示全部楼层
建议lz不要坐那干等match,有小伙伴在G的主动联系manager吧!
回复 支持 反对

使用道具 举报

 楼主| will_ym 发表于 2015-11-21 22:24:10 | 显示全部楼层
sjtucissy 发表于 2015-11-21 21:45
建议lz不要坐那干等match,有小伙伴在G的主动联系manager吧!

多谢建议 已经在努力找小伙伴了 希望这次能match上吧
回复 支持 反对

使用道具 举报

 楼主| will_ym 发表于 2015-11-21 22:27:05 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-21 12:15.1point3acres缃
谢谢回复,我的理解是这样的,一个点能否在这一时刻到达有两个条件:1.周围有在之前能够到达点 2.当前雨水 ...

两个方法都行 dp那个确实是每次都需要遍历一下整个二维数组的

多谢多谢 希望这次能match成功
回复 支持 反对

使用道具 举报

 楼主| will_ym 发表于 2015-11-21 22:30:29 | 显示全部楼层
maomaoxiong 发表于 2015-11-21 15:22. 1point3acres.com/bbs
恭喜楼主。第四题跟哪个LC比较像?

word break.....
回复 支持 反对

使用道具 举报

 楼主| will_ym 发表于 2015-11-21 22:30:37 | 显示全部楼层
queeniejing 发表于 2015-11-21 15:40. more info on 1point3acres.com
同问第四题 感谢楼主

word break.....
回复 支持 反对

使用道具 举报

nash142857 发表于 2015-11-22 00:21:45 | 显示全部楼层
想问下楼主dp咋搞?
回复 支持 反对

使用道具 举报

zwcelesta 发表于 2015-11-22 00:44:50 | 显示全部楼层
求问楼主:
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第二题dfs跟dp的复杂度各是多少啊?假设要雨水高度最后是k。那就是做k次dfs。也就是k*n*m。如果dp每更新一次都要扫一遍矩阵的话,那不也是k*n*m吗?有啥优化?
回复 支持 反对

使用道具 举报

 楼主| will_ym 发表于 2015-11-22 01:18:36 | 显示全部楼层
nash142857 发表于 2015-11-22 00:21
想问下楼主dp咋搞?

见楼上。。。。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 02:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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