一亩三分地论坛

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

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

回报G家新鲜面经

[复制链接] |试试Instant~ |关注本帖
bearkoala 发表于 2016-10-15 01:49:02 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 全职@Google - 猎头 - 技术电面 |Passfresh grad应届毕业生

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

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

x
贡献一个G家新鲜的电面面经。面试官是个美国人,很nice,迟到了10分钟,说是因为一开始用的电话是坏的,又临时换了一个会议室的电话再打。。一开始先问了我之前的博士题目,我大概找了一个项目说了一下,过去了大概10分钟吧。然后就开始做题,一共本该是45分钟,但是我们挂电话的时候已经比原定结束时间晚了15分钟。也就是整个talk的时间大概是50分钟吧。。

我的题挺基本挺简单的:
给一个2D的grid, grid上面每一个element是一个character. 然后给一个input的单词,找出在这个2维grid里面所有可能match这个单词的path的集合。
input: 2D grid, string word. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
output: 所有单词的path的集合

我开始问基本问题,可以向哪些方向移动? 他说可以简单假设上下左右。 返回的是路径,那需要怎么表示?我问用pair<i,j> 可以吗?他说,that's a good strategy. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

然后说了一下大概的思路,用DFS,然后就开始写code.
我写的时候还怕太安静,偶尔还说一下我在做什么,他整个过程安静,也没有一直跟我说话。

写了一会,给他看我完成的版本,他看了一会,然后问,在我的DFS子函数里面,输入的变量,比如 vector<vector<int>> & Vst, 为什么要用derefence符号“&”。然后我的子函数的code里面,为什么要把Vst[i][j]设为1,做DFS, 然后再把Vst[i][j]改回0. 然后问了一下 vector<vector<int>> & Vst 和vector<vector<int>>  Vst 的区别

第二个follow up,就是问复杂度,我一开始有点蒙,跟他说我想一下,他说好的你慢慢想,也没有一直问我跟我说话. 假设二维数组一共有A个element,单词长度是B, 我一开始觉得是O(A^B), 后来又好好想了想,写出来应该是 O(4*3^(B-1)*A),他很惊讶,说我说的是对的,他要是自己想的话,会直接说O(4^B*A), 然后我笑了笑说仔细想想是有个小trick在里面的,不过我们讨论的很开心。

这时候时间已经超了,他还问我,这个题如果不用DFS,还可以用什么方法做?不要求我写整个代码,说说思路,我说可以用BFS,但是一个global的visited数组不会work,要用特殊方法记录每一个path之前已经访问过的信息。他说好,时间到了,我们就到这里吧。

总的来说题目做出来了,follow up也答得差不多,没有非常快的给出答案,但是在讨论和自己想了想之后,还是能答对的。面试官非常nice,这个要非常谢谢他。
昨天上午面的,今天早晨一大早收到recruiter电话,还以为是要挂了,结果他说feedback非常好,要move forward to onsite。继续努力拼一拼,lz不是纯cs编程出身,所以求更多Bless..

a598165394 发表于 2016-10-15 04:53:32 | 显示全部楼层
好奇请教一下题主,复杂度为什么不是O(3^(B-1)*A) 啊~
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2016-10-15 09:14:16 | 显示全部楼层
a598165394 发表于 2016-10-15 04:53
好奇请教一下题主,复杂度为什么不是O(3^(B-1)*A) 啊~

是(3^(B-1))*A的意思吗?
回复 支持 反对

使用道具 举报

hezhifeng850207 发表于 2016-10-15 13:32:23 来自手机 | 显示全部楼层
a598165394 发表于 2016-10-15 04:53.鐣欏璁哄潧-涓浜-涓夊垎鍦
好奇请教一下题主,复杂度为什么不是O(3^(B-1)*A) 啊~

因为第一个字母有4个可能方向,后面b-1个字母每个有3个可能方向
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-10-15 22:22:16 | 显示全部楼层
hezhifeng850207 发表于 2016-10-15 13:32
因为第一个字母有4个可能方向,后面b-1个字母每个有3个可能方向

有道理额,谢谢了!
回复 支持 反对

使用道具 举报

a598165394 发表于 2016-10-15 22:22:30 | 显示全部楼层
sunnyroom 发表于 2016-10-15 09:14. 1point 3acres 璁哄潧
是(3^(B-1))*A的意思吗?
-google 1point3acres
楼下的那个是正解
回复 支持 反对

使用道具 举报

larry_cn 发表于 2016-10-15 23:08:40 | 显示全部楼层
这个是 以前的 一道面经 . 1point 3acres 璁哄潧
如果 记录每个 字符的位置 再做的话 时间复杂度 是 O(matrix size)
回复 支持 反对

使用道具 举报

362802781 发表于 2016-10-16 00:41:32 | 显示全部楼层
求问google电话面试的大概过程是什么样呀。 打到手机上语音聊天? 然后在google docs里写code?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 10:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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