Katkat
Back

Implement Task Dependencies and Failure

PerplexitySoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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 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.
  1. add_dependency(task_id, dependency_id)
  • Record that task_id depends on dependency_id.
  • A task can have multiple dependencies and multiple dependents.
  1. 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.
  1. 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.