一亩三分地论坛

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

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

Google电面面经

[复制链接] |试试Instant~ |关注本帖
superbeet 发表于 2016-4-18 12:47:14 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Pass在职跳槽

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

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

x
Google 电面面经。从留学申请时就从地里学到很多,今天希望回报论坛,也为Onsite攒攒人品。

是个白人小哥,人很耐心,很看重思维过程。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

题目是Leetcode海岛题变种,把岛改成了Google Map上的山峰。问如何计算地图上有多少做山峰。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
15分钟写完,编test case,修了个Bug。
Follow up one: 如果地图数据经常会更新,每次都要算山峰数量,如何提高效率。
Follow up two: 有什么其他算法可以完成题目,除了DFS和Union-Find Set。
Follow up three: 如果地图数据量特别大,单机处理不了怎么办。要求说思路或写伪代码。
-google 1point3acres
两周后Onsite,感觉有些紧张,望各位大大传授一些实战经验。. 鍥磋鎴戜滑@1point 3 acres
另请教各位大大,General software engineering interview是什么,被告知Onsite会有这个面试。

评分

1

查看全部评分

Alice0701 发表于 2016-4-18 21:46:11 | 显示全部楼层
请教一下follow up 1&2 楼主是怎么答的啊? 谢谢
回复 支持 反对

使用道具 举报

edcent 发表于 2016-4-19 00:50:24 | 显示全部楼层
同问 followup 楼主都是怎么答的?
回复 支持 反对

使用道具 举报

 楼主| superbeet 发表于 2016-4-19 01:20:54 | 显示全部楼层
edcent 发表于 2016-4-19 00:50
同问 followup 楼主都是怎么答的?

follow up one - 我感觉他是想问island II里那种情况,经常添加或更新新地图信息。因为这题只要求岛屿得数量,并不要知道具体的位置。可以用Union-find set做。每更新几个点就把那几个点做一下union-find操作,这样以前已经算过的数据就不用再算了,速度就快了。

follow up two - 我说可以用DP做,把每个点左上角区域的岛的数量算一下。本质上和union-find set的意思是差不多的。然后他就问了large scale情况。

follow up three - 其实就是应该用map reduce做。但是我没用过,然后就说了思路,然后最后提到了map reduce,面试官好像感觉挺满意。
回复 支持 反对

使用道具 举报

 楼主| superbeet 发表于 2016-4-19 01:21:10 | 显示全部楼层
Alice0701 发表于 2016-4-18 21:46. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
请教一下follow up 1&2 楼主是怎么答的啊? 谢谢

在楼下回复了~
回复 支持 反对

使用道具 举报

jialegavin 发表于 2016-4-19 01:47:02 | 显示全部楼层
superbeet 发表于 2016-4-19 01:21-google 1point3acres
在楼下回复了~

楼主你好,follow up one的话,需要考虑山峰消失的情况么?还有follow up two的large scale的话要怎么弄呢, 多谢楼主。
回复 支持 反对

使用道具 举报

 楼主| superbeet 发表于 2016-4-19 02:01:29 | 显示全部楼层
jialegavin 发表于 2016-4-19 01:47
楼主你好,follow up one的话,需要考虑山峰消失的情况么?还有follow up two的large scale的话要怎么弄 ...

没有问山峰消失这种情况。如果可以删除,那就只能以这个点周围的点开始DFS或者BFS了,因为删掉的那个点有可能把一座山分成两座。

large scale主要就是要考虑boundary和怎么传信息,大矩阵的分成小矩阵注意不能丢失信息。
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-4-19 02:08:37 | 显示全部楼层
superbeet 发表于 2016-4-19 01:20
follow up one - 我感觉他是想问island II里那种情况,经常添加或更新新地图信息。因为这题只要求岛屿得 ...

谢谢楼主分享!!
回复 支持 反对

使用道具 举报

小艾哥 发表于 2016-4-19 02:29:54 | 显示全部楼层
楼主,一般面试问到类似follow up 3这样输入数据很大单机处理不了的问题是不是思路都是map reduce?有没有什么资料是介绍这种类型题目的答题技巧的?
回复 支持 反对

使用道具 举报

jialegavin 发表于 2016-4-19 04:20:14 | 显示全部楼层
superbeet 发表于 2016-4-19 02:01
没有问山峰消失这种情况。如果可以删除,那就只能以这个点周围的点开始DFS或者BFS了,因为删掉的那个点有 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
恩恩,懂了
谢谢楼主分享!
回复 支持 反对

使用道具 举报

 楼主| superbeet 发表于 2016-4-19 04:35:29 | 显示全部楼层
有没有人知道General software engineering interview指的是什么?
回复 支持 反对

使用道具 举报

zoufengboy 发表于 2016-4-19 07:44:09 | 显示全部楼层
superbeet 发表于 2016-4-19 04:35
有没有人知道General software engineering interview指的是什么?

就是general hire不定组

想问一下楼主,原题是1代表山峰,0代表平地,然后连着一起的1算一座山峰?

你能说一下Follow up 2 咋做的吗?因为如果用DP只depend on left/above,但是这题会改变周围四个方向,不太确定这个DP咋做?
回复 支持 反对

使用道具 举报

 楼主| superbeet 发表于 2016-4-20 01:13:13 | 显示全部楼层
对,面试是SWE General hire。Recruiter跟我说Onsite会有三轮General software engineering interview,其中有1-2轮是System Design, 那剩下的那2-1有可能是啥呢?

其实DP我觉得没什么速度优势,不过面试官追问还有没有其它方法,所以急中生智想到了DP。我感觉可以用DP Matrix,存好左上角区域有几个岛。然后计算下一个DP值的时候,从之前几个DP submatrix的边界点开始BFS。不过我感觉速度不会快到哪去,估计也不是常用方法,因为space complexity太大了,面试官也没有再追问转移方程是啥。
回复 支持 反对

使用道具 举报

edcent 发表于 2016-4-20 06:56:24 | 显示全部楼层
楼主,followup要求写代码了吗?
回复 支持 反对

使用道具 举报

 楼主| superbeet 发表于 2016-4-20 08:26:57 | 显示全部楼层
edcent 发表于 2016-4-20 06:56
楼主,followup要求写代码了吗?

不需要,更多就是聊天看你怎么思考的。
回复 支持 反对

使用道具 举报

 楼主| superbeet 发表于 2016-4-22 15:47:10 | 显示全部楼层
zoufengboy 发表于 2016-4-19 07:44
就是general hire不定组

想问一下楼主,原题是1代表山峰,0代表平地,然后连着一起的1算一座山峰?


对,面试是SWE General hire。Recruiter跟我说Onsite会有三轮General software engineering interview,其中有1-2轮是System Design, 那剩下的那2-1有可能是啥呢?. Waral 鍗氬鏈夋洿澶氭枃绔,
. From 1point 3acres bbs
其实DP我觉得没什么速度优势,不过面试官追问还有没有其它方法,所以急中生智想到了DP。我感觉可以用DP Matrix,存好左上角区域有几个岛。然后计算下一个DP值的时候,从之前几个DP submatrix的边界点开始BFS。不过我感觉速度不会快到哪去,估计也不是常用方法,因为space complexity太大了,面试官也没有再追问转移方程是啥。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 16:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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