FastPrepFilter Undesired Comments and Their Descendants

Filter Undesired Comments and Their Descendants

Reddit logoReddit● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

Comments are numbered by array index. parent[i] is -1 for a root or the ID of comment i's parent. animal[i] is cat, dog, or neutral.

A user whose preference is cat considers dog comments undesired, and vice versa. Return every undesired comment plus every descendant of any undesired comment, sorted by ID. Neutral comments are included only when they descend from a marked comment.

Function

undesiredCommentIds(parent: int[], animal: String[], preference: String) → int[]

Examples

Example 1

parent = [-1,0,0,1,1]animal = ["neutral","dog","cat","cat","neutral"]preference = "cat"return = [1,3,4]

Comment 1 is undesired, so both of its descendants are included regardless of label.

Example 2

parent = [-1,0,0]animal = ["dog","cat","neutral"]preference = "dog"return = [1]

Only the cat-labeled child is undesired.

Constraints

  • 0 <= parent.length <= 100000; both arrays have equal length.
  • The parent links form a forest.
  • preference is cat or dog.

More Reddit problems

See Reddit hiring insights
public int[] undesiredCommentIds(int[] parent, String[] animal, String preference) {
  // write your code here
}
parent[-1,0,0,1,1]
animal["neutral","dog","cat","cat","neutral"]
preference"cat"
expected[1,3,4]
Checking account…