一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1980|回复: 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里,不要一个一个搜。我没有理解到。所以他就让我按老思路写了。估计是这轮挂了


Second Round: 

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

评分

1

查看全部评分

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

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

使用道具 举报

stormy1991 发表于 2015-11-14 07:32:28 | 显示全部楼层
lz是多长时间收到面试的啊?
回复 支持 反对

使用道具 举报

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

使用道具 举报

eko910817 发表于 2015-11-16 14:11:11 | 显示全部楼层
不是很明白第二道题是什么意思?
回复 支持 反对

使用道具 举报

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是多长时间收到面试的啊?

. From 1point 3acres bbs大概一周
回复 支持 反对

使用道具 举报

 楼主| hwberg 发表于 2015-11-17 02:53:44 | 显示全部楼层
kurtwang 发表于 2015-11-14 07:10. visit 1point3acres.com for more.
可能是第一轮的问题吧
按照面试官的解法,时间复杂度是NxN
先把所有距离设为INT_MAX

回头跟同学讨论才恍然大悟。google bar太高
回复 支持 反对

使用道具 举报

 楼主| hwberg 发表于 2015-11-17 02:54:33 | 显示全部楼层
queeniejing 发表于 2015-11-14 08:01. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
多谢LZ 分享, 请问第二轮是一道题还是 分开的两道啊?

两道哈。
第一道是找补集
回复 支持 反对

使用道具 举报

 楼主| 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
楼主好~问一下第二题的第二问怎么做哈?第一反应时并查集,但是一想overlap并不存在传递性,A和Boverlap,B ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
这题隐藏两种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。
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (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 ...

. visit 1point3acres.com for more.嗨~多谢回复,第一条明白~第二条想请教一下~如果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的?举例 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
说错了..有点绕.
应该是: 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):.鏈枃鍘熷垱鑷1point3acres璁哄潧
懂了,确实可以做到O(m*n)
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 00:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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