d***d
发帖数: 99 | 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. |
s*****y
发帖数: 897 | |
s*****y
发帖数: 897 | 3 actually it is o(n) not only o(nlogn);
【在 s*****y 的大作中提到】
: looks the same as this one:
: look at 1337's code
: http://www.mitbbs.com/article_t/JobHunting/31898169.html
|
r*******y
发帖数: 1081 | 4 deepest nodes?
optimize
maximum.
【在 d***d 的大作中提到】
: 一道大公司诡异的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.
|
c****p
发帖数: 6474 | 5 我猜DP可做？
optimize
maximum.
【在 d***d 的大作中提到】
: 一道大公司诡异的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.
|
d*******d
发帖数: 2050 | |
d***d
发帖数: 99 | 7 wow..... then i totally screwed this question.... :( |
i*****e
发帖数: 63 | 8 The difference here is you should avoid adding duplicate values.
So, an additional hashmap is needed?
【在 s*****y 的大作中提到】
: looks the same as this one:
: look at 1337's code
: http://www.mitbbs.com/article_t/JobHunting/31898169.html
|
s*****y
发帖数: 897 | |
