谷歌onsite面经

hychin

yurun 发表于 2018-4-7 08:10
额，应该说是一个人既可以是manager也可以是peer，一个manager可以有多个peer但是一个peer只能有一个mana ...

这个题union find + hashmap即可搞定

yurun

hychin 发表于 2018-4-7 08:23
这个题union find + hashmap即可搞定

我一开始也这样想，但是union find会合并根节点，有些manager和peer的关系会消失

foreveriii3

yurun 发表于 2018-4-7 08:01
首先求出来所有最高高度低于上界的路线数量，再用总路线数量减去这个就好了

好方法！
确实是我想复杂了

zestypanda87

yurun 发表于 2018-4-7 08:22
说错了时间复杂度O(n)，空间复杂度sublinear

直接反转linkedlist两次不是空间只要O（1）么？
楼主可以解释下sqrt（n）的做法么？是要并行么？
谢谢！

yurun

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

zestypanda87

yurun 发表于 2018-4-7 12:31
哦，面试官说不可以修改list。每隔sqrt n个node存一个node，然后从最后一个存的node开始反向打印每个subl ...

懂了就是先存sqrt（N）个node，然后每次打印再用一个sqrt（n）的stack
谢谢你！

bdhmwz

yurun 发表于 2018-4-7 08:30
我一开始也这样想，但是union find会合并根节点，有些manager和peer的关系会消失

根结点指针可以表示兄弟关系，节点中另设一个指针指向manager，在路径压缩和merge过程中更新

alanlxl

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

iamafrican

请问第一题怎么做呢

markpen

第三轮是简单的多叉树结构么？如果是的话，是不是可以从当前结点B一直向回溯的根结点，检查这条路径上是否有A，有的话A 就是B 的manager，否则的话不是。如果存在奇怪的环，那就只能遍历了。