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 Technical Screen rounds at Bytedance.

What role is this question designed for?

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

Count Target-Sum Paths in an N-ary Tree | Bytedance Coding Question

Count Target-Sum Paths in an N-ary Tree

Company: Bytedance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given the root of an N-ary tree. Each node contains an integer value and a list of zero or more child nodes. You are also given an integer `targetSum`. A valid path is any downward path that starts at any node and ends at any node in that node's subtree. The path must follow parent-to-child edges, but it does not need to start at the root or end at a leaf. Return the number of valid downward paths whose node values sum to exactly `targetSum`. Design an algorithm with `O(n)` time complexity, where `n` is the number of nodes in the tree. Example: ```text 10 / | \ 5 -3 2 / | \ \ \ 3 2 1 11 3 ``` If `targetSum = 8`, valid paths include `5 -> 3` and `5 -> 2 -> 1`, so the answer includes at least those paths.

Quick Answer: This question evaluates a candidate's competency in tree data structures and traversal algorithms, specifically counting path sums in N-ary trees and managing cumulative state for efficient aggregation.

You are given an N-ary tree and an integer targetSum. To make the tree easy to serialize, the tree is represented by two arrays: - values[i] is the integer value stored in node i - children[i] is a list of the indices of node i's children If the tree is non-empty, node 0 is the root. If values is empty, the tree is empty. A valid path is any downward path that starts at any node and ends at any node in that node's subtree. The path must follow parent-to-child edges, but it does not need to start at the root or end at a leaf. A single node also counts as a path. Return the number of valid downward paths whose node values sum exactly to targetSum. Design an algorithm that runs in O(n) time, where n is the number of nodes in the tree.

Constraints

0 <= n <= 200000, where n = len(values)
len(children) == n
For n > 0, the child lists describe a valid rooted N-ary tree with node 0 as the root
-10^9 <= values[i], targetSum <= 10^9
The answer fits in a signed 64-bit integer

Examples

Input: ([10, 5, -3, 2, 3, 2, 1, 11, 3, 1], [[1, 2, 3], [4, 5, 6], [7], [8], [], [9], [], [], [], []], 8)

Expected Output: 3

Explanation: The valid paths are 5 -> 3, 5 -> 2 -> 1, and -3 -> 11.

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

Expected Output: 3

Explanation: The three valid paths are root -> left, root -> right, and left -> its child.

Input: ([], [], 5)

Expected Output: 0

Explanation: An empty tree has no paths.

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

Expected Output: 1

Explanation: The single node itself forms one valid path.

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

Expected Output: 8

Explanation: Every downward path in this tree sums to 0, and there are 8 such paths in total.

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

Expected Output: 4

Explanation: The valid paths are 1 -> -1 on the left, 1 -> -1 on the right, -1 -> 1 on the left branch, and -1 -> 1 on the right branch.

Hints

Instead of starting a new DFS from every node, count how many valid paths end at the current node.
Maintain prefix sums along the current root-to-node path. If the current prefix sum is S, then every earlier prefix sum equal to S - targetSum forms a valid path ending here.

Quick Overview

This question evaluates a candidate's competency in tree data structures and traversal algorithms, specifically counting path sums in N-ary trees and managing cumulative state for efficient aggregation.