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 Uber.

What role is this question designed for?

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

Compute sums and max path in N-ary tree

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given the root of an **N-ary tree** (each node can have 0..k children). Implement the `Node` class yourself. Assume each node stores an integer `value` and a list of child nodes `children`. Complete the following tasks: 1. **Sum of all nodes**: Return the sum of `value` over **all** nodes in the tree. 2. **Maximum path value**: Define a *path* as a sequence of nodes from the **root to any leaf** (a node with no children). The *path value* is the sum of node values along that path. Return the **maximum** root-to-leaf path value. 3. **Return the max path**: Return the list of node values along one root-to-leaf path that achieves the maximum path value from (2). If multiple paths tie, you may return any one of them. ### Input / Output - Input: `root: Node | null` - Output: - (1) an integer total sum - (2) an integer maximum root-to-leaf path sum - (3) an array/list of integers representing the values along the chosen max path ### Notes / Constraints - The tree can be empty (`root = null`). - Node values can be negative, zero, or positive. - Aim for linear time in the number of nodes.

Quick Answer: This question evaluates implementation and traversal skills for N-ary tree data structures, including recursion/DFS techniques, aggregation of node values, and tracking root-to-leaf path sums.

Sum of an N-ary Tree

Given an N-ary tree encoded as [value, children], return the sum of all node values.

Constraints

Each non-empty node is [value, children]

Examples

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

Expected Output: 10

Explanation: Nested children.

Input: (None,)

Expected Output: 0

Explanation: Empty tree.

Input: ([-5, []],)

Expected Output: -5

Explanation: Single negative node.

Hints

DFS every node exactly once.

Maximum Root-to-Leaf Path Sum in an N-ary Tree

Return the largest sum along any root-to-leaf path.

Constraints

Each non-empty node is [value, children]

Examples

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

Expected Output: 8

Explanation: Chooses 1->3->4.

Input: (None,)

Expected Output: None

Explanation: Empty tree.

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

Expected Output: -3

Explanation: All negative values.

Hints

The best path from a node is its value plus the best child path.

Return a Maximum Root-to-Leaf Path

Return one list of node values whose root-to-leaf sum is maximum.

Constraints

Ties may return any maximum path; this solution chooses the first best child.

Examples

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

Expected Output: [1, 3, 4]

Explanation: Returns values on the best path.

Input: (None,)

Expected Output: []

Explanation: Empty tree.

Input: ([5, []],)

Expected Output: [5]

Explanation: Single node path.

Hints

Compute the best child path recursively and prepend the current value.

Quick Overview

This question evaluates implementation and traversal skills for N-ary tree data structures, including recursion/DFS techniques, aggregation of node values, and tracking root-to-leaf path sums.