How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at ZipHQ.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at ZipHQ during technical interviews.

Compute maximum sum in a tree without adjacency

Quick Overview

This question evaluates dynamic programming on trees and graph component identification by requiring selection of non-adjacent nodes to maximize a sum, targeting skills in tree algorithms, constraint-based optimization, and rigorous correctness and complexity reasoning.

Company: ZipHQ

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given a tree where each node has an integer value, select a subset of nodes to maximize the sum under the constraint that if you choose a node, you cannot choose any of its children (i.e., no parent–child pair can both be chosen). Implement a function that returns the maximum achievable sum. Describe your algorithm, justify correctness, and analyze time and space complexity. Follow-up: How would you handle a forest (multiple disconnected trees)? Explain how you would identify components and compute the overall result.

Quick Answer: This question evaluates dynamic programming on trees and graph component identification by requiring selection of non-adjacent nodes to maximize a sum, targeting skills in tree algorithms, constraint-based optimization, and rigorous correctness and complexity reasoning.

Given a rooted tree where each node has an integer value, select a subset of nodes to maximize the total sum subject to the constraint that no node and any of its children may both be chosen (no parent–child pair can both be selected). Return the maximum achievable sum. The subset may be empty (sum 0), which matters when all values are negative. The tree is provided in a flat, array-based form so it is language-agnostic: - `values[i]` is the integer value of node `i`. - `children[i]` is the list of indices of the children of node `i`. - If the tree is non-empty it is rooted at node `0`. An empty tree is represented by empty `values` and `children`. Implement `solution(values, children)` returning the maximum sum. Follow-up (forest / disconnected trees): If the input is a forest with multiple roots, run the same per-subtree DP from each root and sum the per-component maxima. Roots are the nodes that are not the child of any other node; you can find them by computing in-degrees (a node is a root iff no node lists it in its `children`). The overall answer is the sum of max(include, exclude) taken at each root — there is no cross-tree constraint because disconnected trees share no parent–child edges.

Constraints

0 <= n <= 10^5 nodes
Node values are integers that may be negative; the empty subset (sum 0) is allowed
children[i] lists the direct children of node i; the structure forms a valid rooted tree at node 0 when non-empty (no cycles, every non-root node appears exactly once as a child)

Examples

Input: ([3, 2, 1], [[1, 2], [], []])

Expected Output: 3

Explanation: Root 0 has value 3 and two leaf children (2, 1). Choosing the root alone gives 3; choosing both children gives 2+1=3. Both are optimal; the max sum is 3.

Input: ([1, 2, 3, 4, 5], [[1, 2], [3, 4], [], [], []])

Expected Output: 12

Explanation: Tree: 0(1)->{1(2),2(3)}, 1->{3(4),4(5)}. Best is to skip nodes 1 and 2 and take the root plus the grandchildren: 1 + 4 + 5 = 10? No — better to take node 2(3) and the grandchildren 3(4),4(5) while skipping node 1: 3+4+5=12, which beats taking node 1(2)+root. Max = 12.

Input: ([], [])

Expected Output: 0

Explanation: Empty tree: the only valid subset is empty, sum 0.

Input: ([10], [[]])

Expected Output: 10

Explanation: Single node with value 10; choose it for sum 10.

Input: ([-5, -3, -2], [[1, 2], [], []])

Expected Output: 0

Explanation: All values are negative, so the best choice is to select nothing, yielding the empty-subset sum of 0.

Input: ([5, 10, 4, 3, 2], [[1, 2], [3, 4], [], [], []])

Expected Output: 14

Explanation: Tree: 0(5)->{1(10),2(4)}, 1(10)->{3(3),4(2)}. Skipping node 1 to take its children 3(3)+4(2)=5 is worse than taking node 1(10). Optimal: take node 1(10) and node 2(4) (siblings, both excluded only if root is chosen). Don't take root, take 1(10)+2(4)=14. Max = 14.

Input: ([4, 1, 5, 1, 1, 1], [[1, 2], [3], [4, 5], [], [], []])

Expected Output: 7

Explanation: Tree: 0(4)->{1(1),2(5)}; 1(1)->{3(1)}; 2(5)->{4(1),5(1)}. Taking the root 0(4) forces excluding 1 and 2, then take grandchildren 3(1)+4(1)+5(1): 4+1+1+1=7. The alternative of taking 2(5)+1(1) and a grandchild caps lower, so the max is 7.

Hints

Think per-subtree with two states: the best sum if you CHOOSE this node, and the best sum if you DON'T. Combine children bottom-up.
If you choose a node, you must EXCLUDE all its children, so add up each child's exclude-state. If you don't choose it, each child independently takes max(include, exclude).
The answer at the root is max(include_root, exclude_root). Because values can be negative, the empty-subset case naturally falls out (exclude-state of a leaf is 0).
For the forest follow-up, find roots as nodes with in-degree 0 and sum the per-root max over all components.

Quick Overview