Exclude Cat- or Dog-Related Comments and All Their Replies by Reader Mode
Company: Reddit
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given the comments of a discussion thread. Every comment either replies to another comment, its parent, or is top-level, so the comments form one or more trees. Each comment carries two flags that say whether it is about cats and whether it is about dogs.
A reader chooses one of two modes:
- `"CAT_PERSON"`: does not want to see dog-related comments.
- `"DOG_PERSON"`: does not want to see cat-related comments.
If a comment is about the reader's undesired animal, that comment and all of its replies, at every depth, must be excluded. Return the IDs of every excluded comment.
Follow-up: state the time and space complexity of your solution in terms of the number of comments.
### Function Signature
```python
def get_comments_to_exclude(comments: list[dict], mode: str) -> list[int]:
```
Each element of `comments` is a record with these keys:
| Key | Type | Meaning |
|---|---|---|
| `id` | `int` | Unique comment ID |
| `parent_comment` | `int` or `None` | ID of the comment this one replies to, or `None` for a top-level comment |
| `body` | `str` | Comment text |
| `cat` | `bool` | Whether the comment is about cats |
| `dog` | `bool` | Whether the comment is about dogs |
The records are the values of an ID-to-comment dictionary, supplied as a list in arbitrary order; a reply may appear before its parent.
### Rules
- In `"CAT_PERSON"` mode a comment is undesired when `dog` is `True`; in `"DOG_PERSON"` mode, when `cat` is `True`. A comment with both flags set is undesired in both modes.
- A comment is excluded when it is undesired or when any of its ancestors (its parent, its parent's parent, and so on) is undesired. Once an ancestor is undesired, the comment's own flags do not matter.
- `parent_comment` may refer to an ID that does not appear in `comments`. Such a comment is treated as top-level: the missing parent causes no exclusion.
- `body` never affects the result.
- Return the excluded IDs in ascending order, without duplicates. Return `[]` when nothing is excluded.
### Constraints
- `0 <= len(comments) <= 100000`
- IDs are distinct integers with `0 <= id <= 10^9`.
- `parent_comment` is `None` or an integer in the same range, never equal to the comment's own `id`, and following parent links never forms a cycle.
- A reply chain can be as deep as the total number of comments.
- `mode` is exactly `"CAT_PERSON"` or `"DOG_PERSON"`.
### Examples
**Example 1**
```text
Input:
comments = [
{"id": 0, "parent_comment": None, "body": "Look! A cute baby elephant taking a nap!", "cat": False, "dog": False},
{"id": 2, "parent_comment": 1, "body": "I agree!", "cat": False, "dog": False},
{"id": 11, "parent_comment": 0, "body": "Almost as cute as my poodle!", "cat": False, "dog": True}
]
mode = "CAT_PERSON"
Output: [11]
```
Comment 11 is about dogs and has no replies. Comment 2 replies to ID 1, which is not in the input, so it is treated as top-level and kept. In `"DOG_PERSON"` mode the output would be `[]`.
**Example 2**
```text
Input:
comments = [
{"id": 5, "parent_comment": None, "body": "My puppy learned to sit today", "cat": False, "dog": True},
{"id": 6, "parent_comment": 5, "body": "Congratulations!", "cat": False, "dog": False},
{"id": 7, "parent_comment": 6, "body": "Thanks!", "cat": False, "dog": False},
{"id": 8, "parent_comment": 7, "body": "Any training tips?", "cat": False, "dog": False},
{"id": 9, "parent_comment": None, "body": "My cat ignores every command", "cat": True, "dog": False}
]
mode = "CAT_PERSON"
Output: [5, 6, 7, 8]
```
The tree is 5, then 6, then 7, then 8. Comment 5 is about dogs, so it and all its descendants are excluded, even though 6, 7 and 8 carry no flags. In `"DOG_PERSON"` mode the output would be `[9]`.
**Example 3**
```text
Input:
comments = [
{"id": 6, "parent_comment": 5, "body": "Same here", "cat": False, "dog": False},
{"id": 3, "parent_comment": 2, "body": "My dog does that too", "cat": False, "dog": True},
{"id": 1, "parent_comment": None, "body": "What do your pets do all day?", "cat": False, "dog": False},
{"id": 5, "parent_comment": 4, "body": "My cat and my dog nap together", "cat": True, "dog": True},
{"id": 2, "parent_comment": 1, "body": "My cat sleeps on the keyboard", "cat": True, "dog": False},
{"id": 4, "parent_comment": 1, "body": "Mostly sleeping, I assume", "cat": False, "dog": False}
]
mode = "DOG_PERSON"
Output: [2, 3, 5, 6]
```
Comments 2 and 5 are about cats. Comment 3 is about dogs, which this reader wants to see, but it is still excluded because its parent 2 is excluded; comment 6 is excluded as a reply to 5. In `"CAT_PERSON"` mode the output would be `[3, 5, 6]`.
Overview: Given discussion comments that form reply trees, each flagged as being about cats, dogs, both or neither, return every comment a cat person or a dog person should not see, where hiding a comment also hides all of its replies. Tests reasoning over tree structure, edge cases such as missing parents, and complexity analysis.
Read the full Reddit Machine Learning Engineer interview experience this question came from