ORIGINAL CODING QUESTION
Fewest reviewers covering tree edges
Select as few tree nodes as possible so every parent-child edge has at least one selected endpoint. Return the minimum selected-node count.
Original exercise · hard. Editorial role relevance does not imply a company has asked this question.
Input and output
n, followed by n parent IDs. Node 0 is root with parent -1; every other parent is in [0, node ID).
Constraints
1 ≤ n ≤ 200; the parent list describes one connected rooted tree.
Example 1
Input
4 -1 0 0 0
Output
1
Selecting root alone covers every edge.
Example 2
Input
4 -1 0 1 2
Output
2
Two selected nodes cover the chain.
Explain your approach
Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?
Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.
Hint 1
A selected node lets each child choose either state.
Hint 2
An unselected node forces all its children to be selected.
Hint 3
Combine these two states bottom-up.
Practice this question
Save your work privately, explain decisions and return to your revision queue.
Open practice workspaceBrowse the question library →