Filter Comment Subtrees and Analyze Score-Based Retention

Comments form a parent-child forest and each comment is categorized as dog or cat. Given a viewer preference, exclude every opposite-category comment and its entire subtree. Return the excluded comment IDs. ### Constraints and Clarifications For the base practice interface, IDs are unique strings, every nonroot parent exists, parent links are acyclic, and each node has one category. Return IDs in input order as serialization normalization; parents need not appear first. No size bounds are reported. Empty input returns an empty list. ### Part 1 — Preference Filtering For a cat-preferring viewer, remove each dog comment and every descendant, even if a descendant is categorized as cat. Apply the symmetric rule for a dog-preferring viewer. #### What This Part Should Cover Build adjacency independently of record order and avoid repeated traversal when unwanted-category nodes are nested. ### Part 2 — Subtree-Score Follow-up Each comment also has a point value. The follow-up says a subtree whose total exceeds a threshold should be kept, and emphasizes computing the subtree sum starting at every opposite-category comment, including nested ones. Explain how to compute these sums efficiently and identify the policy clarification required when a qualifying subtree is nested inside a subtree that would otherwise be hidden. #### What This Part Should Cover Use the sum over the entire subtree, not the root's own score. Evaluate all relevant roots before applying visibility decisions. Distinguish possible nested-retention precedence rules rather than assuming the report specifies one. ### What a Strong Answer Covers A correct base filter, a linear-time subtree-sum calculation, and a complete explanation of how a stated follow-up policy would affect the final traversal. The base task is the deterministic output contract; the follow-up's precedence must be resolved before grading that extension. ### Follow-up Questions - Why can stopping at the first hidden root skip a qualifying nested subtree? - What happens when a subtree sum equals the threshold?