Round 1
Questions:
-
A connected unweighted undirected graph with
N
nodes andN-1
edges (tree) was given where each node were labeled from0
toN-1
. Also, a valueK
was given as well. Each node has a value, given in anarray
, where the ith index tells the value of the ith Node where0 <= i < N
. The tree is rooted at the 0th Node. You need to collect points from all the node values. Points can be calculated from node values using any two of the given methods.Type 1: Go to a Node say
x
and collectarray[x] - K
to add it to points.
Type 2: Go to a Nodex
, divide node value and all of its subtree node's values by 2 permanently, then add the current node value post dividing (i.e.arr[x]/2
) to points.Calculate the maximum Points which can be collected by using any of the Types (In each node you can choose any type to collect points independently).
Constraints:
1 <= N <= 10^5
-10^5 <= array[i] <= 10^5
-10^9 <= K <= 10^9class Solution { public int maxPoints(int[] edges, int[] nodeValues, int N, int K) { // Write your code here } }
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.