Google Onsite

一个月前面的，第一家面的公司，HR说非常close但是还是挂了。求加点分。
1. 设计一个class，可以实现往里面加interval和给一个value返回这个value在不在之前加的interval里。
2. Game of life，要求每个cell查看少于8个周围c

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

substring containing only 2 unique characters, followup - k characters

kevinwangjk 发表于 2016-9-17 14:41
要删除A和C的关系只能删除A和B或者B和C的关系，不能直接删除A和C。然后如果A->D->C的话，那删除了A和B的 ...

原来是这个意思，那楼主你看看下面这个思路可行吗，
class Person{
  int id;
  Set<Person> directFriend;
  Set<Person> indirectFriend;
}

如果要删除的盆友 B在person A的directFriend里面，那就直接从A的directFriend 中删除B，B的direct friend中删除A。
如果要删除的盆友 B在person A的indirectFriend里面，那就scan A的directFriend set，任意在该set中的friend k,
如果k有direct or indirect friend B,把所有满足条件的k从A的directFriend set中删除。同时更新k的direct friend set。

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

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

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

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

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

请问楼主第三题什么解法啊？

求问第四题思路， 用类似存graph的方法来存吗？
还是用别的什么办法？

小A要当码农 发表于 2016-9-18 04:53
请问楼主第三题什么解法啊？

用的是DFS，起点为所有碰到X=0和Y=1的边的censor，终点是X＝1或者Y＝0的边，如果有一条censor形成的path从任意起点到终点，就表示过不去

补充内容 (2016-9-18 05:01):
X=0或者Y=1

william_gong 发表于 2016-9-18 04:58
求问第四题思路， 用类似存graph的方法来存吗？
还是用别的什么办法？

我想了好久想不出什么好办法，结果他最后提示就是每次删朋友后要重新建立所有有关人的关系图。每个人有一个直接朋友和间接朋友的list。

楼主朋友那题我有个不明白的， 如果A 有朋友B， B有朋友C，那么A和C就是朋友，如果想删除A的朋友C，那要怎么做呢， 在不影响B的朋友关系的情况下？
感觉如果B一直有朋友A和C，那么A和C怎么都没法删除朋友关系？

xpli521 发表于 2016-9-18 05:38
楼主朋友那题我有个不明白的， 如果A 有朋友B， B有朋友C，那么A和C就是朋友，如果想删除A的朋友C，那要怎 ...

要删除A和C的关系只能删除A和B或者B和C的关系，不能直接删除A和C。然后如果A->D->C的话，那删除了A和B的朋友关系，A和C也还是朋友

xpli521 发表于 2016-9-18 05:54
原来是这个意思，那楼主你看看下面这个思路可行吗，
class Person{
  int id;

如果A和B是direct friends，删除了A和B后，还得找到A通过B而得到的各层indirect friends然后更新，然后vice versa。
A和B是indirect friends应该不能直接删除

kevinwangjk 发表于 2016-9-17 14:58
如果A和B是direct friends，删除了A和B后，还得找到A通过B而得到的各层indirect friends然后更新，然后vi ...

求大神解答==