Snowflake·Software Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Snowflake SWE interview with a pretty gnarly tree DP problem. The core concept isn't too bad but the deletion semantics made the recurrence way harder to think through cleanly under pressure.

Questions Asked (1)

You have an N-ary tree where deleting an interior node promotes its children up to the deleted node's parent (order preserved), and the root can never be deleted. Given the root and an integer K representing the maximum allowed height in edges, find the minimum number of node deletions to bring the tree's height down to at most K.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The deletion-promotes-children part is what gets you.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a tree DP where for each node you compute the minimum deletions needed to achieve each possible height, considering that deleting a node promotes its children. Then combine children's results and take the minimum across heights ≤ K at the root.

Pro tip: Clarify the deletion semantics early: deleting an interior node promotes its children to its parent, so the height reduction depends on the subtree structure, not just depth. Also mention that greedy pruning often fails because promoting children can increase height elsewhere.

1. Clarify problem and edge cases

Confirm that deleting a node removes it and promotes its children to its parent, preserving order, and that the root cannot be deleted. Discuss edge cases like K=0 (only root allowed) and already valid trees.

2. Define DP state

For each node u, define dp[u][h] = minimum deletions in subtree of u to make its height ≤ h, assuming u is not deleted. Also consider the option of deleting u, which merges its children into u's parent.

3. Derive recurrence

If u is kept, its height is 1 + max child height, so dp[u][h] = sum over children of min_{h' ≤ h-1} dp[child][h']. If u is deleted, its children become siblings of u's parent, so the cost is 1 + sum of dp[child][h] (same height allowance).

4. Compute bottom-up

Process nodes in post-order. For each node, compute dp[u][h] for h from 0 to K (or up to original height). Use prefix minima over children's dp to optimize the sum.

5. Extract answer and analyze complexity

The answer is dp[root][K] (root cannot be deleted). Time complexity is O(N * K) with prefix minima, space O(N * K). Mention that K can be up to N, so O(N^2) worst-case, but often acceptable.

Key Points to Mention

Tree DP with state (node, height limit) and the two choices: keep or delete the node.
Deleting a node promotes its children to its parent, so the height constraint applies to the merged level.
Use prefix minima over children's DP arrays to compute the sum efficiently.
Root cannot be deleted, so the answer is dp[root][K].
Time complexity O(N * K) and space O(N * K), with potential optimization to O(N * H) where H is original height.
Greedy approaches (e.g., always delete deepest nodes) can fail because promotion can increase height elsewhere.

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