Katkat
Back

Implement a Task Processor

Scale AISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage tasks with dependencies using a combination of graph-based topological sorting (Kahn's algorithm) and a priority queue to ensure deadlines are respected.

Task Processor

You are building a task processing system. You are given a list of tasks, where each task has an ID, a deadline, and a list of prerequisite task IDs that must be completed before the current task can start.

A task can only be processed if all its prerequisites are completed. Among all tasks that are currently available to be processed (i.e., their prerequisites are met), you must always choose the task with the earliest deadline.

Implement the function process_tasks(tasks) which returns a list of task IDs in the order they should be executed.

Input Format

  • tasks: A list of objects/dictionaries, each with:
    • id: Unique integer ID.
    • deadline: Integer representing time.
    • prerequisites: A list of task IDs.

Constraints

  • 1 <= len(tasks) <= 10^5
  • Deadlines and IDs are integers.
  • It is guaranteed that there are no circular dependencies.

Example

tasks = [
    {"id": 1, "deadline": 10, "prerequisites": []},
    {"id": 2, "deadline": 5, "prerequisites": [1]},
    {"id": 3, "deadline": 8, "prerequisites": []}
]
# Output: [3, 1, 2]
# Explanation: Task 3 (deadline 8) and Task 1 (deadline 10) are ready. 
# Task 3 has a smaller deadline, so process it first. 
# Then process 1. Finally, 2 is ready.

Edge Cases

  • Tasks with no prerequisites.
  • Multiple tasks having the same deadline (break ties by ID).

Hints

Hint 1

Represent the tasks as a directed acyclic graph where edges point from a prerequisite to the dependent task.

Hint 2

Use an array or hash map to keep track of the 'in-degree' (number of unfinished prerequisites) for each task.

Hint 3

Maintain a min-heap to store all tasks whose in-degree is 0, ordered by their deadline and then by their ID.

Follow-up questions

  • How would you modify your solution to detect if a circular dependency exists in the input?
  • If multiple tasks become available simultaneously, how does the time complexity change if you need to process them in batches?
  • How would you design the system if tasks can have varying execution durations instead of just deadlines?