How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Perplexity.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Perplexity during technical interviews.

Implement Task Dependencies and Failure | Perplexity Coding Question

Implement Task Dependencies and Failure

Company: Perplexity

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Implement a Python in-memory task manager for an AI workflow system. Each task has a unique `task_id` and a status. A task may depend on other tasks. If task `A` depends on task `B`, then: - `B` is a dependency (parent) of `A` - `A` is a dependent (child) of `B` You must store both directions of the relationship. Implement a class with at least the following behavior: 1. `add_task(task_id)` - Create a new task if it does not already exist. 2. `add_dependency(task_id, dependency_id)` - Record that `task_id` depends on `dependency_id`. - A task can have multiple dependencies and multiple dependents. 3. `fail_task(task_id)` - Mark the given task as failed. - Then cascade the failure to every task that directly or transitively depends on it. - For example, if `C` depends on `B` and `B` depends on `A`, then failing `A` must also fail `B` and `C`. 4. `get_status(task_id)` - Return the current status of the task. Your implementation should handle large dependency graphs efficiently. A naive DFS that repeatedly revisits the same nodes may time out on test cases with hundreds of interconnected tasks.

Quick Answer: This question evaluates understanding of graph-based data structures and algorithms for modeling bidirectional task dependencies, status tracking, and efficient cascading failure propagation in an in-memory task manager.

You are given the method calls that would be made on an in-memory task manager for an AI workflow system. Simulate that manager by processing a list of operations. Each task has a unique string `task_id` and a status. Every new task starts as `"active"`. If task `A` depends on task `B`, then `B` is a dependency (parent) of `A`, and `A` is a dependent (child) of `B`. Your implementation must maintain both directions of this relationship. A failed task causes every task that directly or transitively depends on it to fail as well. For example, if `C` depends on `B` and `B` depends on `A`, then failing `A` must also fail `B` and `C`. Process these operations: - `('add_task', task_id)`: Create the task if it does not already exist. - `('add_dependency', task_id, dependency_id)`: Record that `task_id` depends on `dependency_id`. Repeated edges should have no extra effect. If either task does not exist yet, create it as `"active"` first. If `dependency_id` is already failed, then `task_id` must fail immediately, and that failure must continue cascading to its dependents. - `('fail_task', task_id)`: If the task does not exist yet, create it first. Then mark it as failed and cascade the failure to all direct and transitive dependents. - `('get_status', task_id)`: Return the current status of the task. If the task has never been created or referenced, return `"not_found"`. Return a list containing the results of all `get_status` operations in order. Your solution should be efficient for large graphs with shared downstream tasks or cycles. A naive traversal that revisits the same nodes many times may time out.

Constraints

0 <= len(operations) <= 200000
The total number of unique tasks plus unique dependency edges is at most 200000
Each `task_id` is a string of length 1 to 50
The same task may be added multiple times, and the same dependency may be added multiple times
The dependency graph may contain shared descendants or cycles

Examples

Input: ([('add_task', 'A'), ('add_task', 'B'), ('add_task', 'C'), ('add_dependency', 'B', 'A'), ('add_dependency', 'C', 'B'), ('fail_task', 'A'), ('get_status', 'A'), ('get_status', 'B'), ('get_status', 'C')],)

Expected Output: ['failed', 'failed', 'failed']

Explanation: B depends on A and C depends on B, so failing A cascades to B and then to C.

Input: ([('add_task', 'A'), ('add_task', 'B'), ('add_task', 'C'), ('add_task', 'D'), ('add_task', 'E'), ('add_dependency', 'B', 'A'), ('add_dependency', 'C', 'A'), ('add_dependency', 'D', 'B'), ('add_dependency', 'D', 'C'), ('add_dependency', 'D', 'C'), ('fail_task', 'A'), ('get_status', 'A'), ('get_status', 'B'), ('get_status', 'C'), ('get_status', 'D'), ('get_status', 'E')],)

Expected Output: ['failed', 'failed', 'failed', 'failed', 'active']

Explanation: D is reachable from A through both B and C, but it should still only be failed once. E is unrelated and stays active.

Input: ([('add_task', 'A'), ('add_task', 'B'), ('add_task', 'C'), ('add_dependency', 'C', 'B'), ('fail_task', 'A'), ('add_dependency', 'B', 'A'), ('get_status', 'A'), ('get_status', 'B'), ('get_status', 'C')],)

Expected Output: ['failed', 'failed', 'failed']

Explanation: A fails first. Later, B is declared to depend on failed A, so B must fail immediately, and C fails because it depends on B.

Input: ([('add_task', 'A'), ('add_task', 'B'), ('add_dependency', 'A', 'B'), ('add_dependency', 'B', 'A'), ('fail_task', 'A'), ('get_status', 'A'), ('get_status', 'B')],)

Expected Output: ['failed', 'failed']

Explanation: The cycle should not cause an infinite loop. Once A fails, B fails too, and already failed tasks are not processed again.

Input: ([('get_status', 'missing')],)

Expected Output: ['not_found']

Explanation: The task was never created or referenced, so its status is not_found.

Input: ([],)

Expected Output: []

Explanation: With no operations, there are no status queries to return.

Hints

Use two hash maps of sets: one for each task's dependencies and one for each task's dependents.
Failure only needs to travel from a task to its dependents. Use an iterative DFS/BFS and make sure each task is processed at most once when it becomes failed.

Quick Overview

This question evaluates understanding of graph-based data structures and algorithms for modeling bidirectional task dependencies, status tracking, and efficient cascading failure propagation in an in-memory task manager.