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

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.

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.

Loading coding console...

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.

Quick Overview

Constraints

Examples

Hints