FB实习面经

luckybird 发表于 2017-11-5 02:15
恭喜楼主，求问前两面每次都只有一个题目嘛？有follow up嘛？

是的只有一个题。第一次有followup。小岛就是问各种时间空间复杂度，好像还问了一个增减单个node后，如何判定岛数量的增减。

增减单个node 判定岛数量增减是什么意思呢？

还想问个问题，island的那个题，你是用递归dfs做的嘛？还是用并查集做的呢？

楼主，请问你phd实习 也不问研究内容只要做题么

luckybird 发表于 2017-11-5 09:37
还想问个问题，island的那个题，你是用递归dfs做的嘛？还是用并查集做的呢？

我用的dfs。增减node就是在原有矩阵上，任意一个位置1变0或0变1，问小岛数量有无变化。
这个没写code，只是口述。

prince123 发表于 2017-11-5 14:56
楼主，请问你phd实习 也不问研究内容只要做题么

是的。。估计team match的时候才会问吧。

同祝福！

rippersean 发表于 2017-11-6 01:03
是的。。估计team match的时候才会问吧。

请问楼主岛屿问题follow up 0变1，1变0，岛屿数量影响，你怎么答的呀？用什么方法解决？

king_lm 发表于 2017-11-6 08:52
请问楼主岛屿问题follow up 0变1，1变0，岛屿数量影响，你怎么答的呀？用什么方法解决？

因为我在DFS中把所有1的neighbor都会标记一下，所以只要看变的这个是不是被标记过就行了。若0变1，是则不变，否则加一。
当时面的是0变1没问1变0. 不过我觉得也可以直接看他neighbor有没有1，有则不变，无则减一。

rippersean 发表于 2017-11-6 11:31
因为我在DFS中把所有1的neighbor都会标记一下，所以只要看变的这个是不是被标记过就行了。若0变1，是则不 ...

那如果是这种情况呢？

1. 
   
2. 11011
   
3. 11011
   

复制代码

第一行的0变成了1。。。岛屿数量应该会减1吧