Google Onsite

xpli521 发表于 2016-9-18 06:05
求大神解答==

非大神。。上面已经提到过了，就是要删除的时候重新建立所有间接朋友。。。很慢，但是假设就是删除朋友发生的很少，只要查找两个人是不是朋友快就可以。

请问第一轮那题lz是怎么做的呢？

william_gong 发表于 2016-9-18 07:18
请问第一轮那题lz是怎么做的呢？

用个BST存interval，然后加interval的时候merge重复的，key用lower bound

第三题，能详细说说么?

kevinwangjk 发表于 2016-9-18 06:08
非大神。。上面已经提到过了，就是要删除的时候重新建立所有间接朋友。。。很慢，但是假设就是删除朋友发 ...

在想可不可以这样做：
为每个间接朋友设一个计数器，表示和间接朋友share多少个直接朋友
这样比如原来A-B-C，A和B的连接断掉以后A-C之间的计数器-1，如果计数器是0才删掉间接朋友。这样不用整个重构
加直接朋友的时候也需要更新计数器就是了，但是本来就要检查是否会导致增加间接朋友，所以不会多出多少开销

题很有意思啊
感谢！

hxtang 发表于 2016-9-18 21:26
在想可不可以这样做：
为每个间接朋友设一个计数器，表示和间接朋友share多少个直接朋友
这样比如原来A ...

但是worst case还是一样的，而且也还是要看所有的间接朋友有没有到0。

kevinwangjk 发表于 2016-9-19 02:43
但是worst case还是一样的，而且也还是要看所有的间接朋友有没有到0。

删除A-B的时候肯定是要访问所有A的间接朋友和B的所有间接朋友
我觉得导致慢的可能是对A的每个间接朋友C，还要检查A的直接朋友和C的直接朋友的交集，这个操作不是O(1)的，感觉至少是线性的。但是用计数器的话，就是直接减一下。

不过也许我把不用计数器更新间接朋友的算法想复杂了？

请问第二题怎么算满足不查看周围8个value的要求？

LZ请问 game of life board无限大怎么处理呢?