google onsite

一剑终情 发表于 2018-11-4 10:27
真是旱的旱死，涝的涝死啊。楼主不是很想去的有3轮是面经题，我们这种想去的全是奇葩题????????????

所以要送楼主大米攒人品啊！ 楼主夜以继日刷透了600题，没想到也没什么用武之地了

多谢分享！

dagangdou 发表于 2018-11-4 02:13
统一回答一下。
在MTV总部面的。

感谢楼主回答，可是这样子map没有处理跨块之间的pattern咩？

楼主第二题不是很明白forrest，可以再讲讲吗？O(∩_∩)O谢谢
如果就按题意贪心做，比如[i][j]位置有球，并且i行球数大于1，并且j列球数大于1，则删去[i][j]球，同时--i行球数，--j列球数。这么做不知道行不行。。。

cwjade 发表于 2018-11-4 16:30
楼主第二题不是很明白forrest，可以再讲讲吗？O(∩_∩)O谢谢
如果就按题意贪心做，比如[j]位置有球，并且i ...

楼主的forest其实是指一个连通域，两个球如果在同行或者同列表示联通。贪心应该是不对的，和拿掉的顺序有关系，应该先拿掉degree最小的球。找出连通域的个数，答案就是总球数-连通域个数了

usagi21 发表于 2018-11-4 16:57
楼主的forest其实是指一个连通域，两个球如果在同行或者同列表示联通。贪心应该是不对的，和拿掉的顺序有 ...

连通域是用[i][j]表示吗？如果M*N所有地方都有球，是有M*N个连通域吗？

cwjade 发表于 2018-11-4 17:50
连通域是用[j]表示吗？如果M*N所有地方都有球，是有M*N个连通域吗？

都有球是一个连通域啊

usagi21 发表于 2018-11-4 15:00
感谢楼主回答，可是这样子map没有处理跨块之间的pattern咩？

我的想法是map的多台机器各自处理不同区域中的所有pattern，然后根据pattern不同把结果发给不同的reduce机器做相应的reduce voting哈

usagi21 发表于 2018-11-4 16:57
楼主的forest其实是指一个连通域，两个球如果在同行或者同列表示联通。贪心应该是不对的，和拿掉的顺序有 ...

对的对的，就是这个意思

cwjade 发表于 2018-11-4 17:50
连通域是用[j]表示吗？如果M*N所有地方都有球，是有M*N个连通域吗？

如果所有的地方都有球，那么BFS的时候就可以把他们连成一个区域了。伪代码大概这样：
1 对所有没有visited过的并且有球的地方进行BFS
2 BFS的话这个点的横纵线上所有没有visited过的球都放入queue里并且设置成visited
3 一轮BFS结束后连通区数量加一
4 所有BFS结束后用总球数减去连通区数量