Google 1月11日阳光谷面经(最后一轮神仙题求解答)

richpanda 发表于 2019-2-2 01:35
最后一题有点无向图里面找强链接cluster的意思。解题时只要注意到小于三条边的点肯定是不满足条件，是要剔 ...

感觉说的很有道理，面试的时候根本没想到这么多。就一直在想DFS。。。

cheerier 发表于 2019-2-2 01:44
请问第一题可以用BFS吗？

BFS不行吧，因为机器人是要move的，move了之后它会进入下一个grid。用BFS的话机器人没法走呀。

cheerier 发表于 2019-2-2 01:44
请问第一题可以用BFS吗？

BFS不行吧，因为机器人是要move的，move了之后它会进入下一个grid。用BFS的话机器人没法走呀。

蓝冰 发表于 2019-2-2 03:49
请问转SETI 那当天的 SDE onsite还继续面吗

我是面完onsite之后才让我转的，所以不太清楚。你可以问一下你的HR

sdwrz16 发表于 2019-2-2 04:04
感谢楼主分享,

第二轮没大看懂岛屿的定义, 是有一部分1围成一个圈就可以? 还是说必须全部都是1?

第二题只要是上下左右这四个方向连在一起的就算是同一片岛屿。具体定义可以看做题网站island那道题

jianpanxia 发表于 2019-2-2 08:30
嗯。我当时想的方法是默认所有人都会被邀请，然后再DFS遍历的过程中去一个个排除不会被邀请的人，感觉差 ...

感觉第二题再优化的思路有点像Binary search的意思，提前排除掉一部分搜索空间，比如sum(matrix[0][a], matrix[0][b]) == (b - a + 1) 的时候就可以跳过(a, b)这一段

第二题感觉可以先从水开始bfs得到所有岛屿的boarder 然后对每个岛屿dfs访问，这样就可以获得每个岛屿的边界点 时间复杂度O（nm）

菜鸡弱弱问一句 seti是啥啊

请问是不是得onsite面的可以才能继续加面seti？