← Zip Interview Insights

Zip·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026Remote

Summary

Ziphq coding round threw a tree DP problem at me that looked like a LeetCode classic until I realized the input wasn't a binary tree and I had to build the data structure from scratch myself.

Questions Asked (1)

Q1

Given a general n-ary tree (which you must implement yourself, including the node structure with a children list), find the maximum amount you can collect from nodes such that no node and its direct parent are both selected.

Algorithms & Data Structures
Author's notes

I knew House Robber III going in so my first instinct was to just start coding the DP.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Define a TreeNode class with a value and a list of children, then use tree DP where each node returns two values: the maximum sum when the node is selected (including its value plus the 'not selected' sums of its children) and when it is not selected (sum of the maximum of the two states for each child). The answer is the maximum of the two states at the root.

Pro tip: Clarify whether node values can be negative; if so, adjust the DP to allow skipping nodes (e.g., max(0, ...) for not selected). Also, mention that the DP can be implemented iteratively with post-order traversal to avoid recursion depth issues.

1. Define the Node Structure

Create a class for the n-ary tree node with a value field and a list of children. This sets up the data structure for the problem.

2. Identify the DP State

For each node, define two states: dp[node][0] = max sum when node is not selected, dp[node][1] = max sum when node is selected. Explain the recurrence relations.

3. Derive Recurrence Relations

If node is selected, its children cannot be selected, so dp[node][1] = node.val + sum(dp[child][0]). If node is not selected, children can be either selected or not, so dp[node][0] = sum(max(dp[child][0], dp[child][1])).

4. Choose Traversal Order

Use post-order traversal (DFS) to compute children's DP values before the parent. This can be done recursively or iteratively with a stack.

5. Compute and Return Result

After processing all nodes, the answer is max(dp[root][0], dp[root][1]). Handle edge cases like empty tree or negative values.

Key Points to Mention

  • Tree DP with two states per node (selected/not selected).
  • Post-order traversal to ensure children are processed before parent.
  • Recurrence relations: selected = val + sum(not selected children); not selected = sum(max(selected, not selected) children).
  • Time complexity O(n) and space complexity O(n) for recursion stack or explicit stack.
  • Handling of negative values: if values can be negative, ensure not selecting a node is always an option (e.g., use max(0, ...) for not selected).
  • Implementation details: defining the node class, using a list for children, and possibly iterative DFS to avoid recursion limits.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.