Google Onsite面经，略逗逼

frank94 发表于 2015-12-23 18:38
非计算机专业，看不懂lz说的技术性问题。但还是觉得lz这次一帆风顺啊，实力和运气都有了~

2333 主要是运气好，希望你也能顺利拿到大offer啊

终于看到了~~赞rp

kirkland和mtv比除了消费低还有其他好处吗

appliang 发表于 2015-12-24 16:17
kirkland和mtv比除了消费低还有其他好处吗

没州税，不过秋天冬天天气很烂，没太阳

can't see it

请问楼主 第三轮那个subset的题目   有要求subset必须是联通的吗？
如果不联通，直接dfs一遍找到所有邻居数大于k的点集合就好了。
如果要求联通，同样dfs，不同的是只递归邻居数大于k的邻居结点就好了。
两种情况都是O(n)的时间呢

aiwojiujiu 发表于 2016-1-21 11:56
请问楼主 第三轮那个subset的题目   有要求subset必须是联通的吗？
如果不联通，直接dfs一遍找到所有邻居 ...

这个k是指你找出来的subset里每个节点有k个neighbor，而且这k个neighbor也在subset里

lqzgz 发表于 2016-1-21 12:42
这个k是指你找出来的subset里每个节点有k个neighbor，而且这k个neighbor也在subset里

恩恩 谢谢楼主解答  那请问楼主  dfs能行得通吗
就是说先找到一个neighbor数目大于k的node，然后从他的周围开始dfs，找到所有临近的并且邻居数大于k的node。dfs过程中记录traverse过node最多的数目，就是结果。
这样可以吗？

期待楼主解答

aiwojiujiu 发表于 2016-1-22 09:41
恩恩 谢谢楼主解答  那请问楼主  dfs能行得通吗
就是说先找到一个neighbor数目大于k的node，然后从他的 ...

你的算法我要是没理解错的话，应该不行。比较简单的例子就是，abcd四个点，a-d，b-d，c-d，k=2，你这样应该是从d开始dfs，但是d的neighbor a b c都没有2个neighbor，所以a b c都会从subset中删掉，那么这时候就只剩下d了，因为d这时候已经没有neighbor了，所以d也从subset中删掉。那么，你traverse过node最多的数目是1，也就是你一开始选d做traverse起点，但是，实际上subset里的node个数应该是0

lqzgz 发表于 2016-1-22 14:25
你的算法我要是没理解错的话，应该不行。比较简单的例子就是，abcd四个点，a-d，b-d，c-d，k=2，你这样应 ...

哦 我懂了 是我题目没理解正确  楼主题目的意思是 subset中点的邻居数目不会考虑 subset以外的点的情况。
多谢楼主解答。

还有一个小问题，楼主这道题的临接链表表示图的数据结构，那么为什么删除一个边的时间复杂度是logn呢？
log是哪里来的？