Google internship interview 20151109

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:　


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

guoqinlong 发表于 2015-11-16 21:16
楼主好~问一下第二题的第二问怎么做哈？第一反应时并查集，但是一想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。

补充内容 (2015-11-17 17:21):
改成:　如果 A 是 B 的 child

hwberg 发表于 2015-11-17 02:57
这题隐藏两种inconsitensy：
1. statementI有环
2. 如果 A 和 B 有 overlap， 那 A 就不能跟 B的 ances ...

嗨~多谢回复，第一条明白~第二条想请教一下~如果A和B有overlap,A和B的祖先感觉还是有可能overlap的？举例来说，A是B的爷爷, B是C的爷爷，那么A是C的祖先，但是B可能和A与C均overlap?多谢~~

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)

可能是第一轮的问题吧
按照面试官的解法，时间复杂度是NxN
先把所有距离设为INT_MAX
然后把(each guard,distance=0)放到queue里
每次pop出来一个，检查周围的格子，不是INT_MAX就设为distance+1,然后把这周围几个格子再放到queue里

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

lz是多长时间收到面试的啊？

多谢LZ 分享， 请问第二轮是一道题还是 分开的两道啊？

不是很明白第二道题是什么意思？

楼主好~问一下第二题的第二问怎么做哈？第一反应时并查集，但是一想overlap并不存在传递性，A和Boverlap，B和C overlap并不能说明A和Coverlap?

stormy1991 发表于 2015-11-14 07:32
lz是多长时间收到面试的啊？

大概一周

kurtwang 发表于 2015-11-14 07:10
可能是第一轮的问题吧
按照面试官的解法，时间复杂度是NxN
先把所有距离设为INT_MAX

回头跟同学讨论才恍然大悟。google bar太高

queeniejing 发表于 2015-11-14 08:01
多谢LZ 分享， 请问第二轮是一道题还是 分开的两道啊？

两道哈。
第一道是找补集

eko910817 发表于 2015-11-16 14:11
不是很明白第二道题是什么意思？

是分开两道