pythonadvanced40 minutes

Build a Scalable Task Scheduler with Dependency Resolution in Python

Create a mini-project in Python to implement a task scheduler that executes tasks in the correct order based on their dependencies. The scheduler should detect circular dependencies and optimize for concurrent execution where possible.

Challenge prompt

Design and implement a Python function called 'task_scheduler' which receives a dictionary where keys are task names (strings) and values are lists of dependencies (tasks that must be completed before the key task). Your scheduler should return a list of lists where each inner list represents tasks that can be executed concurrently in that stage. Tasks must only be started after all their dependencies are completed. If circular dependencies exist, raise an exception with an informative message.

Guidance

• Use topological sorting with cycle detection to determine execution order.
• Group all tasks that have no mutual dependencies into the same execution stage for concurrency.
• Ensure the function raises a descriptive exception on circular dependencies.

Hints

• Consider using Depth-First Search (DFS) to detect cycles and generate task order.
• Use a queue or list to track tasks with no remaining dependencies to execute in parallel.
• Model the tasks and dependencies as a directed graph.

Starter code

def task_scheduler(tasks):
    '''
    tasks: dict[str, list[str]] - keys are task names, values their dependencies
    returns: list[list[str]] - stages of concurrently executable tasks
    '''
    # Implement your scheduler here
    pass

Expected output

[['task1', 'task3'], ['task2'], ['task4']] # Example output for given dependencies

Core concepts

topological sortgraph algorithmscycle detectionconcurrency scheduling

Challenge a Friend

Send this duel to someone else and see if they can solve it.