一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 2448|回复: 16
收起左侧

Google internship interview 20151109

[复制链接] |试试Instant~ |关注本帖
hwberg 发表于 2015-11-14 06:59:04 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
First Round: (听口音是老美)
There is a museum organized as NxN room. Some rooms are locked and inaccessible. Other rooms are open and some rooms have guards. Guards can only move north, south, east and west, only through open rooms and only within the museum. For each room, find the shortest distance to a guard。

我说用BFS,从每个guard开始搜,更新distance矩阵。面试官说有更优的解法。我提议dp, 被否了。提示说把guards都放进queue里,不要一个一个搜。我没有理解到。所以他就让我按老思路写了。估计是这轮挂了. visit 1point3acres.com for more.


Second Round: 

. 鍥磋鎴戜滑@1point 3 acres
(1)Set A - B
(2) 有一个村庄,流传着两种statement:-google 1point3acres
1. A 死了之后 B出生。
2. A和B有overlap。
现在有很多这样的statements,要你判断有没有inconsistency.
这轮面的还行。四十分钟做完, 面试官表示做的不错。
不过四天后收到拒信了。请各位帮我分析下,问题在哪. from: 1point3acres.com/bbs

评分

1

查看全部评分

kurtwang 发表于 2015-11-14 07:10:36 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
可能是第一轮的问题吧
按照面试官的解法,时间复杂度是NxN.鐣欏璁哄潧-涓浜-涓夊垎鍦
先把所有距离设为INT_MAX. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后把(each guard,distance=0)放到queue里. From 1point 3acres bbs
每次pop出来一个,检查周围的格子,不是INT_MAX就设为distance+1,然后把这周围几个格子再放到queue里

如果dp最后写对了,复杂度也是最优,那就可能是单纯面试官不爽
回复 支持 反对

使用道具 举报

stormy1991 发表于 2015-11-14 07:32:28 | 显示全部楼层
关注一亩三分地微博:
Warald
lz是多长时间收到面试的啊?
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-11-14 08:01:39 | 显示全部楼层
多谢LZ 分享, 请问第二轮是一道题还是 分开的两道啊?
回复 支持 反对

使用道具 举报

eko910817 发表于 2015-11-16 14:11:11 | 显示全部楼层
不是很明白第二道题是什么意思?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

guoqinlong 发表于 2015-11-16 21:16:30 | 显示全部楼层
楼主好~问一下第二题的第二问怎么做哈?第一反应时并查集,但是一想overlap并不存在传递性,A和Boverlap,B和C overlap并不能说明A和Coverlap?
回复 支持 反对

使用道具 举报

 楼主| hwberg 发表于 2015-11-17 02:53:01 | 显示全部楼层
stormy1991 发表于 2015-11-14 07:32
lz是多长时间收到面试的啊?

大概一周
回复 支持 反对

使用道具 举报

 楼主| hwberg 发表于 2015-11-17 02:53:44 | 显示全部楼层
kurtwang 发表于 2015-11-14 07:10
可能是第一轮的问题吧
按照面试官的解法,时间复杂度是NxN
先把所有距离设为INT_MAX
. more info on 1point3acres.com
回头跟同学讨论才恍然大悟。google bar太高
回复 支持 反对

使用道具 举报

 楼主| hwberg 发表于 2015-11-17 02:54:33 | 显示全部楼层
queeniejing 发表于 2015-11-14 08:01
多谢LZ 分享, 请问第二轮是一道题还是 分开的两道啊?
. 1point3acres.com/bbs
两道哈。
第一道是找补集
回复 支持 反对

使用道具 举报

 楼主| hwberg 发表于 2015-11-17 02:54:44 | 显示全部楼层
eko910817 发表于 2015-11-16 14:11
不是很明白第二道题是什么意思?

是分开两道
回复 支持 反对

使用道具 举报

 楼主| hwberg 发表于 2015-11-17 02:57:44 | 显示全部楼层
guoqinlong 发表于 2015-11-16 21:16.1point3acres缃
楼主好~问一下第二题的第二问怎么做哈?第一反应时并查集,但是一想overlap并不存在传递性,A和Boverlap,B ...

这题隐藏两种inconsitensy:
1. statementI有环
2. 如果 A 和 B 有 overlap, 那 A 就不能跟 B的 ancestors (generated from statement I)有 overlap, vice versa。
我的做法是DFS找环,同时maintain一个ancestor的set。找explore children节点的时候,check他们是不是跟ancestors有overlap。 . more info on 1point3acres.com

补充内容 (2015-11-17 17:21):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
改成: 如果 A 是 B 的 child
回复 支持 反对

使用道具 举报

neal1st 发表于 2015-11-17 05:20:07 | 显示全部楼层
放到Queue里不就是BFS吗。。。。。。
回复 支持 反对

使用道具 举报

 楼主| hwberg 发表于 2015-11-17 09:21:02 | 显示全部楼层
neal1st 发表于 2015-11-17 05:20. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
放到Queue里不就是BFS吗。。。。。。

是..但是保证了每个node只enqueue一次
回复 支持 反对

使用道具 举报

guoqinlong 发表于 2015-11-17 14:17:44 | 显示全部楼层
hwberg 发表于 2015-11-17 02:57
这题隐藏两种inconsitensy:
1. statementI有环
2. 如果 A 和 B 有 overlap, 那 A 就不能跟 B的 ances ...
. From 1point 3acres bbs
嗨~多谢回复,第一条明白~第二条想请教一下~如果A和B有overlap,A和B的祖先感觉还是有可能overlap的?举例来说,A是B的爷爷, B是C的爷爷,那么A是C的祖先,但是B可能和A与C均overlap?多谢~~
回复 支持 反对

使用道具 举报

 楼主| hwberg 发表于 2015-11-17 17:20:25 | 显示全部楼层
guoqinlong 发表于 2015-11-17 14:17
嗨~多谢回复,第一条明白~第二条想请教一下~如果A和B有overlap,A和B的祖先感觉还是有可能overlap的?举例 ...

说错了..有点绕.
应该是: dfs进行到下一步的时候,比如 current node 是 A, 加进了children B. B 不可以跟A以及A的ancestor有overlap
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-7 05:17:07 | 显示全部楼层
kurtwang 发表于 2015-11-14 07:10
可能是第一轮的问题吧
按照面试官的解法,时间复杂度是NxN
先把所有距离设为INT_MAX

这个题要一个guard,一个guard的开始,然后做dfs没有区别吧是O(k *n * n)?k是guard数。可以具体说说这个做法吗?是queue,不断pop出来,然后更新周围的格子?这样时间复杂度也没有提高啊?

补充内容 (2015-12-7 05:20): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
懂了,确实可以做到O(m*n)
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-7 05:32:10 | 显示全部楼层
楼主村庄这道题可以具体说说解法吗?或者给下sudo code?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-25 18:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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