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.

Compute maximum sum in a tree without adjacency

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.

Hints

  1. 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.
  2. 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).
  3. 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).
  4. For the forest follow-up, find roots as nodes with in-degree 0 and sum the per-root max over all components.

Loading coding console...