Zenefits Onsite 一题讨论

原帖地址:mitbbs

一个undirected network without cycle,要求求得节点具有到其他节点的最小
distance,也就是node with min(sum_of_distance_to_other_nodes)。这道题弄了一
些时间,开始直接说对每个点BFS。然后慢慢的讨论优化,因为图无环,最后弄出来的
算法是O(n)的。但是代码只写出来了一半,不过之前跟他讨论得很详细了,也先给出了伪
代码,所以感觉他也满意了。

有人答过如下,没有理解:)

想成是个tree,找出所有的leaf,然后把所有leaf放到一个list里
做reverseBFS, 从leaf开始每走一层就加一个weight(sum(child weight) * 2 + 1),
最终会找到一个root。

然后就是balance tree by weight,
从root开始试每个child,如果把那个child假设成root,
child_weight = root.weight – child.weight + (# of root's child – 1)
找出最小的child_weight,把那个child变成root。
直到root.weight小于任何一个child_weight。
结果好像是O(n + logn) = O(n)?
http://www.mitbbs.com/article/JobHunting/32967735_0.html