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 medium 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 Dependency-Aware To-Do List | Perplexity Coding Question

Implement Dependency-Aware To-Do List

Company: Perplexity

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement an in-memory to-do list in Python for managing tasks and task dependencies. You are given three core types to design: - `TaskStatus`: an enum representing possible task states. - `Task`: a data object representing one task. - `ToDoList`: the main class that stores tasks and exposes operations. A task has at least: - a unique task id - a title or description - a status - zero or more dependency tasks that must complete before this task can run - zero or more dependent child tasks that are blocked by this task Use the following statuses: - `READY`: the task can be worked on now. - `BLOCKED`: the task is waiting for one or more dependencies. - `SUCCEEDED`: the task has completed successfully. - `FAILED`: the task has failed. Implement the following functionality. ### Part 1: Basic CRUD Support basic task operations: 1. Create a task. 2. Retrieve a task by id. 3. Update a task's title or description. 4. Delete a task. 5. List all tasks, or list tasks filtered by status. ### Part 2: Dependencies and cascading status updates Add dependency support. A dependency means: task `B` depends on task `A`, so `B` cannot become `READY` until `A` has `SUCCEEDED`. Implement operations such as: 1. Add a dependency between two existing tasks. 2. Remove a dependency. 3. Change a task's status. 4. Automatically update affected downstream tasks. Required behavior: - When a dependency is added, track both directions: - each task's parent dependencies - each task's child dependents - If a task has any unfinished dependency, it should be `BLOCKED` unless it has already terminally completed or failed. - When a task becomes `SUCCEEDED`, check all tasks that depend on it. If all of a child task's dependencies have succeeded, that child task should become `READY`. - When a task becomes `FAILED`, recursively propagate failure to all tasks that directly or indirectly depend on it. - Avoid inefficient full scans over all tasks for every status update. Large test cases should complete within typical interview time limits. You may assume task ids are unique. Clearly define how you handle invalid operations such as missing ids, duplicate dependencies, self-dependencies, dependency cycles, deleting tasks with dependencies, and status updates on already terminal tasks.

Quick Answer: This question evaluates the ability to design in-memory data structures and algorithms for representing tasks with directed dependencies, manage state transitions and cascading updates, and reason about correctness, performance, and edge cases.

Part 1: Basic CRUD To-Do List

Implement a simple in-memory task manager with no dependencies. Process a sequence of operations over tasks. Each task has a unique integer id, a title, and a status in {'READY', 'BLOCKED', 'SUCCEEDED', 'FAILED'}. Return one result per operation in order. Rules: 'create' fails on a duplicate id or invalid status, 'get' returns None for a missing id, 'update' and 'delete' fail on a missing id, and 'list' returns tasks sorted by id. 'list'(None) returns all tasks, while 'list' with an invalid status returns an empty list.

Constraints

0 <= len(operations) <= 100000
1 <= task_id <= 10^9
Title/description is a string of length 0 to 200
Valid statuses are exactly 'READY', 'BLOCKED', 'SUCCEEDED', and 'FAILED'
For deterministic output, listed tasks must be sorted by task_id

Examples

Input: [('create', 1, 'Write code', 'READY'), ('create', 2, 'Review PR', 'BLOCKED'), ('get', 1), ('update', 2, 'Review pull request'), ('list', None), ('delete', 1), ('list', 'READY')]

Expected Output: [True, True, (1, 'Write code', 'READY'), True, [(1, 'Write code', 'READY'), (2, 'Review pull request', 'BLOCKED')], True, []]

Explanation: Covers normal create, read, update, delete, and list behavior.

Input: [('create', 1, 'A', 'READY'), ('create', 1, 'B', 'FAILED'), ('create', 2, 'C', 'DONE'), ('get', 3), ('update', 3, 'X'), ('delete', 2), ('list', None)]

Expected Output: [True, False, False, None, False, False, [(1, 'A', 'READY')]]

Explanation: Shows duplicate id handling, invalid status handling, and missing-id operations.

Input: []

Expected Output: []

Explanation: Edge case: no operations.

Input: [('create', 5, 'Only', 'SUCCEEDED'), ('list', 'SUCCEEDED'), ('list', 'FAILED'), ('list', 'UNKNOWN')]

Expected Output: [True, [(5, 'Only', 'SUCCEEDED')], [], []]

Explanation: Checks status filtering, including an invalid filter value.

Hints

A hash map keyed by task_id makes create/get/update/delete constant time.
For 'list', build the filtered tuples first, then sort them once by id.

Part 2: Dependency-Aware Tasks With Cascading Updates

Implement an in-memory dependency-aware task manager. Each created task starts in status 'READY' with no dependencies. A dependency ('add_dependency', A, B) means task B depends on task A, so B cannot be ready until A has succeeded. Return one result per operation in order. READY and BLOCKED are derived states: callers may directly set only 'SUCCEEDED' or 'FAILED'. Rules: adding a dependency fails if either id is missing, the ids are equal, the dependency already exists, the dependent task is already terminal, the prerequisite task is already FAILED, or the new edge would create a cycle. Removing a dependency fails if the edge does not exist or the dependent task is terminal. Setting status to 'SUCCEEDED' fails if the task is missing, already terminal, or still has any unfinished dependency. Setting status to 'FAILED' fails if the task is missing or already terminal; on success, the task and every direct or indirect dependent become FAILED. When a task succeeds, only its downstream dependents should be updated; do not rescan all tasks on every change.

Constraints

0 <= len(operations) <= 20000
1 <= task_id <= 10^9
Title/description is a string of length 0 to 200
Valid task statuses are 'READY', 'BLOCKED', 'SUCCEEDED', and 'FAILED'
Direct 'set_status' operations are allowed only for 'SUCCEEDED' and 'FAILED'; 'READY' and 'BLOCKED' are maintained automatically
The dependency graph must remain acyclic

Examples

Input: [('create', 1, 'A'), ('create', 2, 'B'), ('add_dependency', 1, 2), ('get', 2), ('set_status', 1, 'SUCCEEDED'), ('get', 2)]

Expected Output: [True, True, True, (2, 'B', 'BLOCKED', [1], []), True, (2, 'B', 'READY', [1], [])]

Explanation: Task 2 is blocked until task 1 succeeds, then it becomes ready automatically.

Input: [('create', 1, 'A'), ('create', 2, 'B'), ('create', 3, 'C'), ('add_dependency', 1, 2), ('add_dependency', 2, 3), ('set_status', 1, 'FAILED'), ('list',)]

Expected Output: [True, True, True, True, True, True, [(1, 'A', 'FAILED', [], [2]), (2, 'B', 'FAILED', [1], [3]), (3, 'C', 'FAILED', [2], [])]]

Explanation: A failure propagates recursively through the dependent chain.

Input: [('create', 1, 'A'), ('create', 2, 'B'), ('create', 3, 'C'), ('add_dependency', 1, 2), ('add_dependency', 2, 3), ('add_dependency', 3, 1), ('add_dependency', 1, 1), ('add_dependency', 1, 2), ('remove_dependency', 1, 2), ('get', 2)]

Expected Output: [True, True, True, True, True, False, False, False, True, (2, 'B', 'READY', [], [3])]

Explanation: Shows cycle rejection, self-dependency rejection, duplicate rejection, and unblocking after dependency removal.

Input: [('create', 1, 'Solo'), ('set_status', 9, 'FAILED'), ('set_status', 1, 'READY'), ('set_status', 1, 'SUCCEEDED'), ('set_status', 1, 'FAILED'), ('get', 1)]

Expected Output: [True, False, False, True, False, (1, 'Solo', 'SUCCEEDED', [], [])]

Explanation: Missing ids fail, READY cannot be set manually, and terminal tasks cannot be updated again.

Input: []

Expected Output: []

Explanation: Edge case: no operations.

Hints

Store both directions of each dependency: parents and children. That makes downstream updates local.
Maintain, for each task, how many dependencies have not yet succeeded. Then a child becomes READY exactly when this count drops to 0.

Quick Overview

This question evaluates the ability to design in-memory data structures and algorithms for representing tasks with directed dependencies, manage state transitions and cascading updates, and reason about correctness, performance, and edge cases.