# Propagate Task Filtering Through Ancestors Tasks form a forest. Each task has a unique integer `id`, a `parent_id` or no parent, and a boolean `directly_filtered` produced by an upstream rule. A task must be removed when it is directly filtered or when any ancestor is removed. Input records may appear in any order. Structural validation must inspect every record, including components that already contain a directly filtered task. For example: ```text Task 1: parent = none, directly_filtered = true Task 2: parent = 1, directly_filtered = false Task 3: parent = 2, directly_filtered = false Task 4: parent = none, directly_filtered = false ``` Only Task 4 remains visible; Tasks 2 and 3 inherit Task 1's filtered state. Design an algorithm that computes the visible task IDs. Explain the invariant, complexity, handling of arbitrary input order, and how production code should respond to a missing parent or a cycle. The upstream direct-filter rule itself is outside this captured problem. ### Clarifying Questions to Ask - Are task IDs unique, and is every nonroot parent expected to exist? - Must visible IDs preserve input order or use another deterministic ordering? - Should malformed cycles fail the whole request or quarantine only the affected component? ### What a Strong Answer Covers - An ID-to-task index independent of input ordering. - Memoized ancestor evaluation or downward propagation from roots. - A proof that one filtered ancestor removes every depth of descendants. - Linear time and space for a valid forest. - Explicit detection and reporting of cycles and missing parents. ### Follow-up Questions - How would you update visibility efficiently when one task's direct flag changes? - How would you preserve stable ordering after filtering? - What tests catch the mistake of checking only a task's immediate parent?