Zenefits Onsite 一题讨论 - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - Zenefits Onsite 一题讨论

相关主题
● binary tree的最长root leaf path	● Find a sub tree with min weight怎么做
● 请教一个C++问题	● 渣渣cs本科半应届如何找工作
● twitter 面经(Update)	● [包子求助] Graph matching problem
● LCA复杂度是多少	● Given a node of a tree, find all nodes on the same level
● LCA复杂度	● MS onsite 面经
● mirror 一个binary tree, 用non-recursive解法怎么做	● G家电面面经--佛云了~~
● 插入节点到complete binary tree的末尾	● 贡献A家面经
● FB面经	● 一道linkedin的graph题

相关话题的讨论汇总
话题: child话题: weight话题: root话题: zenefits话题: onsite

进入JobHunting版参与讨论

(共1页)

m****i
发帖数: 650

一个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

(共1页)

进入JobHunting版参与讨论

相关主题
● 一道linkedin的graph题	● LCA复杂度
● 贡献G电估计挂了	● mirror 一个binary tree, 用non-recursive解法怎么做
● 为人父母，发面经，攒人品，求REFER	● 插入节点到complete binary tree的末尾
● L家onsite面经	● FB面经
● binary tree的最长root leaf path	● Find a sub tree with min weight怎么做
● 请教一个C++问题	● 渣渣cs本科半应届如何找工作
● twitter 面经(Update)	● [包子求助] Graph matching problem
● LCA复杂度是多少	● Given a node of a tree, find all nodes on the same level

相关话题的讨论汇总
话题: child话题: weight话题: root话题: zenefits话题: onsite

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天