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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Netflix.

What role is this question designed for?

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

Compute subtree sums with tree DFS | Netflix Coding Question

Quick Overview

This question evaluates proficiency in tree traversal and aggregation techniques, specifically computing subtree sums using depth-first search while handling traversal state and constraints such as negative values and large n.

hard
Netflix
Coding & Algorithms
Software Engineer

Compute subtree sums with tree DFS

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given an undirected tree with `n` nodes labeled `1..n` and `n-1` edges. The tree is rooted at node `1`. Each node `i` has an integer value `val[i]`. Return an array `subtreeSum[1..n]` where `subtreeSum[u]` is the sum of `val[x]` over all nodes `x` in the subtree of `u` (including `u`). Constraints: - `1 <= n <= 2e5` - Values can be negative. - The input is guaranteed to be a tree. Implement an `O(n)` solution using DFS.

Quick Answer: This question evaluates proficiency in tree traversal and aggregation techniques, specifically computing subtree sums using depth-first search while handling traversal state and constraints such as negative values and large n.

You are given an undirected tree with n nodes labeled from 1 to n, rooted at node 1. Each node i has an integer value val[i]. Return a list of length n where the element at index i-1 is the sum of values of all nodes in the subtree of node i, including node i itself. Your solution should run in O(n) time.

Constraints

1 <= n <= 2 * 10^5
len(edges) == n - 1
-10^9 <= val[i] <= 10^9
The input graph is guaranteed to be a tree
Values may be negative

Examples

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

Expected Output: [15, 2, 9, 3, 5]

Explanation: Node 3 has subtree {3,4,5} with sum 1+3+5=9. Node 1 includes all nodes, so its sum is 15.

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

Expected Output: [2, 1, 4, -1]

Explanation: Node 2 has subtree sum -2+4+(-1)=1, and node 1 has 1+1=2.

Input: (1, [], [-7])

Expected Output: [-7]

Explanation: A single node's subtree consists only of itself.

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

Expected Output: [6, 1, 1, 3, 2, 1]

Explanation: This is a chain. Compute from the end upward: node 6=1, node 5=2, node 4=3, node 3=1, node 2=1, node 1=6.

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

Expected Output: [0, 0, 0, 0]

Explanation: All node values are zero, so every subtree sum is zero.

Hints

Build an adjacency list for the tree, then run DFS from node 1 while tracking each node's parent.

Loading coding console...