Task Processor: Dependencies and Deadlines

hard

CodingReported Jun 2026 · Medium frequency

Requirements

Build a class or service that provides two main actions:
- AddTask(tasks): register one or more tasks with the scheduler.
- ConsumeTask(): select and remove the eligible task whose deadline is earliest.
In Part 1, the input is a collection of tasks containing an id and a deadline. Typical inputs use string identifiers and integer deadline values, for example:

[{"id": "A", "deadline": 5}]

Part 1 rules:
- Tasks have no prerequisite relationships.
- Calling ConsumeTask() removes and returns the task with the minimum deadline.
- When nothing can be consumed, return the specified empty-task result; some formulations call this a "no task" response.
Part 2 introduces subtasks, which lists prerequisite task ids:

[{"id": "A", "deadline": 5, "subtasks": ["B", "C"]}]

A task is not eligible until every task named in its subtasks list has been consumed.
Of the tasks that are eligible at that moment, choose the one with the lowest deadline.
Part 3 extensions:
- updateDeadline(task_id, new_deadline) changes the deadline of a task that remains unconsumed.
- If that task was already consumed, return None or reject the request in another way.
Further discussion topics:
- The runtime cost of every operation.
- Validating tasks, confirming the graph is a DAG, and responding to cycles.
- Concurrent access when several consumers run simultaneously.
- Accepting tasks as a stream instead of receiving one complete batch.
- Designing production-quality unit tests.

A dependency-order scenario from this problem family:

[
  {"id": "A", "deadline": 3, "subtasks": ["B"]},
  {"id": "B", "deadline": 8, "subtasks": []}
]

Although task A has the sooner deadline, it cannot run until task B is consumed. Therefore, the consumption sequence is B followed by A.

Practice cycle detection independently using DFS coloring or Kahn's algorithm so that the DAG-validation follow-up can be addressed quickly.
Create tests covering an empty ready queue, deadline ties, a parent blocked by a child, an update before consumption, an update after consumption, and obsolete heap entries.

hard

CodingReported Jun 2026 · Medium frequency

Build a class or service that provides two main actions:
- AddTask(tasks): register one or more tasks with the scheduler.
- ConsumeTask(): select and remove the eligible task whose deadline is earliest.
In Part 1, the input is a collection of tasks containing an id and a deadline. Typical inputs use string identifiers and integer deadline values, for example:

[{"id": "A", "deadline": 5}]

Part 1 rules:
- Tasks have no prerequisite relationships.
- Calling ConsumeTask() removes and returns the task with the minimum deadline.
- When nothing can be consumed, return the specified empty-task result; some formulations call this a "no task" response.
Part 2 introduces subtasks, which lists prerequisite task ids:

[{"id": "A", "deadline": 5, "subtasks": ["B", "C"]}]

A task is not eligible until every task named in its subtasks list has been consumed.
Of the tasks that are eligible at that moment, choose the one with the lowest deadline.
Part 3 extensions:
- updateDeadline(task_id, new_deadline) changes the deadline of a task that remains unconsumed.
- If that task was already consumed, return None or reject the request in another way.
Further discussion topics:
- The runtime cost of every operation.
- Validating tasks, confirming the graph is a DAG, and responding to cycles.
- Concurrent access when several consumers run simultaneously.
- Accepting tasks as a stream instead of receiving one complete batch.
- Designing production-quality unit tests.

A dependency-order scenario from this problem family:

[
  {"id": "A", "deadline": 3, "subtasks": ["B"]},
  {"id": "B", "deadline": 8, "subtasks": []}
]

Although task A has the sooner deadline, it cannot run until task B is consumed. Therefore, the consumption sequence is B followed by A.

Practice cycle detection independently using DFS coloring or Kahn's algorithm so that the DAG-validation follow-up can be addressed quickly.
Create tests covering an empty ready queue, deadline ties, a parent blocked by a child, an update before consumption, an update after consumption, and obsolete heap entries.