We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design Task Manager

Difficulty: Medium

Problem Description

Design a task management system that allows users to manage their tasks, each associated with a priority. The system should efficiently handle adding, modifying, executing, and removing tasks.

Key Insights

  • Each task is identified by a unique taskId and is associated with a userId and a priority.
  • Tasks can be added, edited, removed, and executed based on priority.
  • The task with the highest priority should be executed first. In case of ties, the task with the higher taskId should be executed.
  • Efficient data structures are necessary to handle up to 200,000 operations.

Space and Time Complexity

Time Complexity:

  • Adding a task: O(log n) (where n is the number of tasks, due to heap operations)
  • Editing a task: O(log n) (if using a priority queue)
  • Removing a task: O(log n) (if using a priority queue)
  • Executing the top task: O(log n) (due to heap operations)

Space Complexity: O(n) for storing tasks and additional space for data structures.

Solution

To implement the TaskManager, we can utilize a combination of a hash map and a priority queue (min-heap or max-heap). The hash map will allow for O(1) access to tasks based on their taskId, while the priority queue will facilitate efficient retrieval and removal of the task with the highest priority.

  1. Data Structures:

    • A hash map to store tasks with as the key and a tuple of <userId, priority> as the value.
    • A priority queue (max-heap) to efficiently access the task with the highest priority.

  2. Operations:

    • Add: Insert the task in the hash map and the priority queue.
    • Edit: Update the priority of the task in the hash map and adjust its position in the priority queue.
    • Remove: Delete the task from the hash map and the priority queue.
    • Execute Top: Retrieve the task with the highest priority from the priority queue, remove it from the hash map and return the associated userId.

Code Solutions

import heapq

class TaskManager:
    def __init__(self, tasks):
        self.task_map = {}
        self.max_heap = []
        for userId, taskId, priority in tasks:
            self.add(userId, taskId, priority)

    def add(self, userId, taskId, priority):
        self.task_map[taskId] = (userId, priority)
        heapq.heappush(self.max_heap, (-priority, -taskId))

    def edit(self, taskId, newPriority):
        userId, _ = self.task_map[taskId]
        self.task_map[taskId] = (userId, newPriority)
        heapq.heappush(self.max_heap, (-newPriority, -taskId))

    def rmv(self, taskId):
        del self.task_map[taskId]

    def execTop(self):
        while self.max_heap:
            priority, taskId = heapq.heappop(self.max_heap)
            priority = -priority
            taskId = -taskId
            if taskId in self.task_map and self.task_map[taskId][1] == priority:
                del self.task_map[taskId]
                return self.task_map[taskId][0]
        return -1
← Back to All Questions