i5已成昨日黄花# Hardware - 计算机硬件
d*d
1 楼
一道大公司诡异的complete binary tree max sum of 2 nodes 题
当场 40min white board 给出了O(N2) 的解法,对方表示赞许,但是没时间optimize
了。直觉告诉我应该有NlogN的解法。大牛指点下。
具体如下:
given one complete binary tree, with positive and identical values in all
nodes.
Find 2 nodes, such that:
sum of their path nodes to root (identical nodes will count only once) are maximum.
当场 40min white board 给出了O(N2) 的解法,对方表示赞许,但是没时间optimize
了。直觉告诉我应该有NlogN的解法。大牛指点下。
具体如下:
given one complete binary tree, with positive and identical values in all
nodes.
Find 2 nodes, such that:
sum of their path nodes to root (identical nodes will count only once) are maximum.