DE Shaw | Online Assessment | Collect maximum points from Tree | Jan 2025

Round 1

Questions:

1. Min-cost-to-remove-all-array-elements

2. A connected unweighted undirected graph with N nodes and N-1 edges (tree) was given where each node were labeled from 0 to N-1. Also, a value K was given as well. Each node has a value, given in an array, where the ith index tells the value of the ith Node where 0 <= 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 collect array[x] - K to add it to points.
   Type 2: Go to a Node x, 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^9

   class Solution {
       public int maxPoints(int[] edges, int[] nodeValues, int N, int K) {
           // Write your code here
       }
   }