周末读物之聊聊三观

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 2551|回复: 7
收起左侧

回报G家新鲜面经

[复制链接] |试试Instant~
我的人缘0
bearkoala 发表于 2016-10-15 01:49:02 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩

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

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

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

x
贡献一个G家新鲜的电面面经。面试官是个美国人,很nice,迟到了10分钟,说是因为一开始用的电话是坏的,又临时换了一个会议室的电话再打。。一开始先问了我之前的博士题目,我大概找了一个项目说了一下,过去了大概10分钟吧。然后就开始做题,一共本该是45分钟,但是我们挂电话的时候已经比原定结束时间晚了15分钟。也就是整个talk的时间大概是50分钟吧。。
. 1point 3acres 论坛.1point3acres网
我的题挺基本挺简单的:
给一个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在里面的,不过我们讨论的很开心。. from: 1point3acres

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

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


上一篇:FB面试被reschedule,phone interview vs 校招 选择
下一篇:linkedin 电面

本帖被以下淘专辑推荐:

  • · Google|主题: 459, 订阅: 125
我的人缘0
a598165394 发表于 2016-10-15 04:53:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
好奇请教一下题主,复杂度为什么不是O(3^(B-1)*A) 啊~
回复

使用道具 举报

我的人缘0
sunnyroom 发表于 2016-10-15 09:14:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (71)
 
 
4% (3)  踩
a598165394 发表于 2016-10-15 04:53
好奇请教一下题主,复杂度为什么不是O(3^(B-1)*A) 啊~
. 牛人云集,一亩三分地
是(3^(B-1))*A的意思吗?
回复

使用道具 举报

我的人缘0
hezhifeng850207 发表于 2016-10-15 13:32:23 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
a598165394 发表于 2016-10-15 04:53
好奇请教一下题主,复杂度为什么不是O(3^(B-1)*A) 啊~

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

使用道具 举报

我的人缘0
a598165394 发表于 2016-10-15 22:22:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
hezhifeng850207 发表于 2016-10-15 13:32
因为第一个字母有4个可能方向,后面b-1个字母每个有3个可能方向

有道理额,谢谢了!

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
a598165394 发表于 2016-10-15 22:22:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
sunnyroom 发表于 2016-10-15 09:14
是(3^(B-1))*A的意思吗?
. 留学申请论坛-一亩三分地
楼下的那个是正解
回复

使用道具 举报

我的人缘0
larry_cn 发表于 2016-10-15 23:08:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (100)
 
 
2% (3)  踩
这个是 以前的 一道面经
如果 记录每个 字符的位置 再做的话 时间复杂度 是 O(matrix size)
回复

使用道具 举报

我的人缘0
362802781 发表于 2016-10-16 00:41:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
求问google电话面试的大概过程是什么样呀。 打到手机上语音聊天? 然后在google docs里写code?
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-22 20:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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