Hyderate the Nodes

Question

Recently I gave a coding interview test at a company. This was one of the problem I was unable to solve. I tried on my own and came with approach but I'm not sure if it's correct, please help me rectify my mistake in approach if any.

This was the problem statement :-

Hydrate the nodes There is a tree with n nodes. The tree is rooted at node with number 0. As usually in computer science, the tree grows upside down comparing to trees existing in nature. Apples grow on nodes of this tree. Some of these apples are underhydrated, some are overhydrated, and others are neither. You know that for each overhydrated apple you'll get overhydratedPenalty cents and for every underhydrated you'll get underhydratedPenalty cents. Now, you want to pour water on exactly one node of the tree. When you pour water on node v, all apples that are in v's subtree, i.e. vitself and all descendants of v, will be hydrated and in consequence, each hydrated apple that was almost overhydrated becomes overhydrated. Moreover, every apple in the whole tree that was almost underhydrated and no water was poured on it gets underhydrated. Calculate the minimum total penalty you can get from pouring water on exactly one node of the tree.

Function Description Complete the function minimumPouringWaterPenalty(vector parent, vector waterLevel, int overhydratedPenalty, int underhydratedPenalty)

minimumPouringWaterPenalty has the following parameter(s): 1. An integer array, parent, of size n, where parenti, denotes the parent of the ith node. 2. An integer array, waterLevel, of size n, where waterLevel denotes the level of the water in the apple on node i. It's either -1, 0 or 1 where -1 stands for almost underhydrated, O stands for neither almost underhydrated nor almost overhydrated and 1 stands for almost overhydrated. 3. An integer, overhydratedPenalty, denoting the penalty for each overhydrated apple. 4. An integer, underhydrated Penalty, denoting the penalty for each underhydrated apple.

The function must return the minimum penalty that you can get by pouring water on exactly one node of the tree.

Text taken from : https://codeforces.com/blog/entry/86512

My approach :

1. Make Graph with parent[i] -> i (g)
2. Do dfs traversal to check penalty at each node if that node is given water. In this just checking if any value is 1 then increase count penalty of overhyderate for that node and store in array(h_penalty) for each node what is penalty if water is given.
3. Traverse again this time check if water is not given then what is penalty for underhyderate. In this just checking if any value is -1, then increase count of penalty of underhyderate for that node and store in array(u_penalty) for each node what is penalty if water is given.
4. Now, I have penalty of each node if water is given and if water is not given. Then I will traverse h_penalty and and for each node I will take minimum of h_penalty[i] + (u_penalty[0]-u_penalty[i]).

Here is my code for approach :

from collections import defaultdict


def hyderatedtheNode(parent, waterLevel, overHyderatd, underHyderated):
    g = defaultdict(list)

    h_penalty = [0] * len(waterLevel)
    u_penalty = [0] * len(waterLevel)

    createGraph(parent, g)
    dfs(0, waterLevel, overHyderatd, underHyderated, 1, h_penalty, g)
    dfs(0, waterLevel, underHyderated, overHyderatd, - 1, u_penalty, g)
    # print(h_penalty)
    # print(u_penalty)
    # print(g)
    # print(list(enumerate(waterLevel)))
    ans = float('inf')
    p = u_penalty[0]
    for i, h in enumerate(h_penalty):
        ans = min(ans, h + (p - u_penalty[i]))
    print(ans)


def createGraph(parent, g):
    for i in range(1, len(parent)):
        g[parent[i]].append(i)


def dfs(src, waterLeve, oH, uH, apple, val, g):
    if not g.get(src, None):
        if waterLeve[src] == apple:
            val[src] = oH
            return oH
        return 0

    if g.get(src, None):
        penalty = 0
        if waterLeve[src] == apple:
            penalty = oH
        for t in g[src]:
            penalty += dfs(t, waterLeve, oH, uH, apple, val, g)
            # print(src, t, penalty)
    val[src] = penalty
    return penalty


hyderatedtheNode([-1, 0, 1], [1, 1, 1], 3, 5)  # 0
hyderatedtheNode([-1, 0, 0], [1, -1, -1], 10, 15)   # 10
hyderatedtheNode([-1, 0, 0, 1], [0, 0, 0, 0], 10, 15)  # 0 
hyderatedtheNode([-1, 0, 1, 0, 1, 2, 2, 2, 5, 5], [-1, -1, 0, -1, 0, 0, 1, 0, 0, 1], 2, 3)  # 4

Please let me know if this approach is fine or any thing else is needed ?

Answer 1

1. Make the tree by given relation (it's a K node tree where K denotes the children of any parent).
2. Calculate the count of underhydrated, overhydrated apples for each node (where each node = self + children value) in the subtree including the node via DFS.
3. Calculate the penalty if no water is poured by root DFS value.
4. Calculate penalty if water poured on each node by its DFS value and check for global min.

public class Main {

    public static void main(String[] args) {
        System.out.println(hyderatedtheNode(new int[]{-1, 0, 1}, new int[]{-1, -1, -1}, 3, 5) == 0);
        System.out.println(hyderatedtheNode(new int[]{-1, 0, 0}, new int[]{1, -1, -1}, 10, 15) == 10);
        System.out.println(hyderatedtheNode(new int[]{-1, 0, 0, 1}, new int[]{0, 0, 0, 0}, 10, 15) == 0);
        System.out.println(hyderatedtheNode(new int[]{-1, 0, 1, 0, 1, 2, 2, 2, 5, 5}, new int[]{-1, -1, 0, -1, 0, 0, 1, 0, 0, 1}, 2, 3) == 4);


    }

    public static int hyderatedtheNode(int[] parent, int[] water, int oh, int uh) {
        Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < parent.length; i++) {
            map.putIfAbsent(parent[i], new ArrayList<Integer>());
            map.get(parent[i]).add(i);
        }
        int[][] waterLevel = new int[parent.length][2];
        for (int[] arr : waterLevel) {
            Arrays.fill(arr, -1);
        }
        dfs(0, waterLevel, water, map);

        int ifNoWater = waterLevel[0][0] * oh + waterLevel[0][1] * uh;
        int globalMin = ifNoWater;
        for (int i = 0; i < parent.length; i++) {
            int currMax = 0;
            currMax -= waterLevel[i][1] * uh;
            globalMin = Math.min(globalMin, (ifNoWater + currMax));
        }
        return globalMin;
    }

    private static int[] dfs(int node, int[][] waterLevel, int[] water, Map<Integer, List<Integer>> map) {
        int[] total = new int[2];
        total[0] = 0; // oh
        total[1] = 0; // uh
        if (water[node] > 0) {
            total[0] += 1;
        } else if (water[node] < 0) {
            total[1] += 1;
        }

        if (waterLevel[node][0] != -1) {
            return waterLevel[node];
        }
        if (map.get(node) != null) {
            for (int i : map.get(node)) {
                int[] temp = dfs(i, waterLevel, water, map);
                total[0] += temp[0];
                total[1] += temp[1];
            }
        }

        waterLevel[node] = total;
        return total;
    }
}

Answer 2

@pkd Your solution works. For bigger test cases, Just increase the recursion limit as you may exceed recursion depth.

import sys
sys.setrecursionlimit(10**6)