JB
BAN USER
Comments (5)
Reputation 30
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
2
of 2 vote
foreach node in the branch which is no more than K deep, get:
W - max weight collected one way from the root to this node (this is a sum of the parent W and the weight of the edge taken)
D - depth traversed to this node
E - an incident edge with maximum value (edge to the parent or a child)
M - maximum collectible weight if jumping back and forth along the edge E
M = W + V * (K - D)
Maximum of M is the answer.
For example for K = 5, the maximum M is in the left most leaf, M = 29 + 24 * 3 = 101. Note that the leaves are not pictured by the author..
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
this is minimum spanning tree problem (look for it in wikipedia).
- JB February 06, 2015Honestly, it does not really look like an interview question.