Implement A Prioritized Task Scheduler With Parent Dependencies

Question

Design and implement a prioritized task scheduler that can manage tasks with parent dependencies, ensuring that tasks are executed in the correct order based on their dependencies.

Codemia · Accepted Answer

To implement a prioritized task scheduler with parent dependencies, we need to ensure that:
1. Each task can have multiple dependencies.
2. Tasks are executed only after their dependencies are completed.
3. Tasks have different priority levels that affect the order of execution.

We can represent the tasks and their dependencies using a directed graph where each node is a task and edges represent dependencies. A priority queue can be used to manage the execution order based on task priority. The algorithm will involve topological sorting to ensure that tasks are executed in the correct order.

The implementation will involve:
1. Creating a class `Task` that contains the task details, priority, and a list of dependencies.
2. Using a dictionary to map tasks to their dependencies.
3. Implementing a priority queue to fetch the next task based on priority.
4. Using Kahn's algorithm for topological sorting to handle dependencies.

This approach is efficient for managing tasks with dependencies. However, if tasks are frequently added or removed, it may require re-evaluating the priority queue. To scale, we could consider distributed task scheduling or implementing a more complex graph structure to handle larger sets of tasks.

Here is a simple Python implementation of the task scheduler:
```python
import heapq
from collections import defaultdict, deque

class Task:
    def __init__(self, name, priority):
        self.name = name
        self.priority = priority
        self.dependencies = []

class TaskScheduler:
    def __init__(self):
        self.tasks = {}
        self.indegree = defaultdict(int)
        self.graph = defaultdict(list)

def add_task(self, task):
        self.tasks[task.name] = task
        self.indegree[task.name] = 0

def add_dependency(self, task_name, dependency_name):
        self.graph[dependency_name].append(task_name)
        self.indegree[task_name] += 1

def schedule(self):
        priority_queue = []
        for task_name, task in self.tasks.items():
            if self.indegree[task_name] == 0:
                heapq.heappush(priority_queue, (task.priority, task_name))

result = []
        while priority_queue:
            priority, task_name = heapq.heappop(priority_queue)
            result.append(task_name)
            for neighbor in self.graph[task_name]:
                self.indegree[neighbor] -= 1
                if self.indegree[neighbor] == 0:
                    heapq.heappush(priority_queue, (self.tasks[neighbor].priority, neighbor))

return result
```
This code defines a `TaskScheduler` that can add tasks, manage dependencies, and schedule tasks based on their priorities.

Implement A Prioritized Task Scheduler With Parent Dependencies

Rippling

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Rippling Software Engineer Interview Guide

Related Questions

Design a scalable Search System

Design a Video Streaming for Rippling

Design a Load Balancing Service

Design a Image Processing Service

Build a high-throughput Image Processing Pipeline