Filter Undesired Comments and Their Descendants
Problem statement
Comments are numbered by array index. parent[i] is -1 when comment i starts a thread, or the ID of the comment it replies to. animal[i] is cat, dog, or neutral, and points[i] is the comment's points.
A user whose preference is cat does not want dog comments, and a user who prefers dog does not want cat comments. These are the undesired comments. A neutral comment is never undesired, and neither is a comment with the preferred label.
The subtree total of a comment is its own points plus the points of all its descendants. An undesired comment stays if its subtree total is greater than threshold. Otherwise it is removed, and removing a comment also hides all of its descendants, whatever their labels.
Check every undesired comment, including one inside the subtree of an undesired comment that stays. A subtree total always counts the whole original subtree, even the parts that end up hidden.
Return the IDs of all hidden comments in ascending order.
In the first part of the interview there was no points rule, and every undesired comment was removed. A threshold of 1000000000 gives that behavior, because no subtree total can be greater than it.
Function
undesiredCommentIds(parent: int[], animal: String[], preference: String, points: int[], threshold: int) → int[]Examples
Example 1
parent = [-1,0,0,1,1]animal = ["neutral","dog","cat","cat","neutral"]preference = "cat"points = [5,1,2,3,4]threshold = 1000000000return = [1,3,4]The user prefers cats, so dog comments are undesired. Comment 1 is the only dog comment. Its subtree is comments 1, 3 and 4, with a total of 1 + 3 + 4 = 8 points, which is not greater than 1000000000. So comment 1 is removed and comments 3 and 4 are hidden with it, whatever their labels.
Example 2
parent = [-1,0,0]animal = ["dog","cat","neutral"]preference = "dog"points = [0,0,0]threshold = 0return = [1]The user prefers dogs, so only the cat comment, comment 1, is undesired. Its total is 0, which is not greater than 0, so it is removed. The neutral comment 2 stays: a neutral comment is never undesired.
Example 3
parent = [-1,0,1,1,3,0]animal = ["neutral","dog","neutral","dog","cat","dog"]preference = "cat"points = [1,4,2,1,3,6]threshold = 6return = [3,4,5]The dog comments are 1, 3 and 5. Comment 1 has a total of 4 + 2 + 1 + 3 = 10 points, which is greater than 6, so it stays. Comment 3 sits inside comment 1's subtree but is still checked on its own: its total is 1 + 3 = 4, so comments 3 and 4 are hidden. Comment 5 has a total of exactly 6, which is not greater than 6, so it is hidden too.
Example 4
parent = [3,-1,1,-1]animal = ["neutral","cat","neutral","cat"]preference = "dog"points = [2,5,0,1]threshold = 4return = [0,3]Parents can have larger IDs than their children, and there can be several roots. Comment 1 is a cat comment with a total of 5 + 0 = 5, which is greater than 4, so it stays. Comment 3 is a cat comment with a total of 1 + 2 = 3, so it is removed and its child, comment 0, is hidden with it. The answer is sorted by ID.
Constraints
0 <= n <= 10000, wherenis the length ofparent,animal, andpoints.parent[i]is-1or an ID from0ton - 1other thani, and following parents from any comment always reaches-1. There can be several threads, a parent can have a larger ID than its child, and one thread can be a single chain ofncomments.animal[i]iscat,dog, orneutral.preferenceiscatordog.0 <= points[i] <= 10000and0 <= threshold <= 1000000000, so every subtree total fits in a 32-bit integer.