Exclude Opposite-Category Comments and Their Descendants

Each comment has a unique ID, a parent comment ID or no parent, and a dog or cat category. For a dog-preferring viewer, exclude every cat comment and all descendants of those comments. For a cat-preferring viewer, apply the symmetric rule. Return the IDs to exclude. ### Constraints and Clarifications For the base practice contract, parent links form a finite forest, every nonroot parent is present, and each comment has exactly one of the two categories. IDs are unique strings; return excluded IDs in input-record order as output normalization. Input order need not place parents before children. No size bounds were reported. The matching rule is absence of the unwanted category, not a requirement for an additional positive preference flag. A descendant's own preferred category does not rescue it from an excluded ancestor. ### Example For a dog-preferring viewer, suppose a cat root has a dog child and that child has a dog child. All three IDs are excluded. A separate dog root remains visible. ### Score Follow-up The reported follow-up says a comment with score strictly above a threshold should still be shown. Clarify whether this exception overrides only that comment's hiding or also restores descendants, and whether a visible child may appear under a hidden parent. Discuss a concrete chosen policy without silently changing the base task's output contract. ### What a Strong Answer Covers Build parent-to-children adjacency, traverse unwanted-category roots and their descendants without duplicate output, and explain graph size and traversal complexity. Address the score exception's ambiguous precedence explicitly. ### Follow-up Questions - Why is it incorrect to keep every dog comment independently for a dog-preferring viewer? - What validation would be needed if parent links could contain cycles or missing IDs?