Design Task Manager
Asked at Apple
Problem
Design a task manager system that supports adding, executing, and removing tasks with priorities, and querying the highest-priority task efficiently.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Medium | View all Apple questions → |
How to Think About It
Brute force: store tasks in a list, scan all tasks for every operation. Add and remove are O(n), get is O(n).
Use a max-heap to get the highest-priority task in O(1) but removal by task ID becomes O(n) without extra bookkeeping.
Combine a HashMap of task ID to priority with a TreeMap or heap for ordered access. The HashMap gives O(1) lookup by ID.
For removal, mark tasks as invalid in the heap lazily rather than rebuilding the heap, giving amortized O(log n) per operation.
A TreeSet or sorted set of (priority, taskId) pairs supports add, remove, and get-max all in O(log n).
Example walkthrough: add(task1, p=5), add(task2, p=3), add(task3, p=5). Heap has [(5,1),(3,2),(5,3)]. exec(task2) removes it. exec(task1) removes it. get() returns task3 with priority 5.
Optimal Approach
Step 1: Maintain a HashMap from task ID to its current priority, and a TreeMap (or TreeSet) keyed by (priority, task ID) for ordered access.
Step 2: addTask(taskId, priority) puts the entry in the HashMap and inserts (priority, taskId) into the TreeSet. Time: O(log n).
Step 3: editTask(taskId, newPriority) looks up the old entry in the HashMap, removes it from the TreeSet, then inserts the new (newPriority, taskId). Time: O(log n).
Step 4: rmTask(taskId) looks up the entry in the HashMap, removes it from the TreeSet, and deletes from the HashMap. Time: O(log n).
Step 5: execTask() peeks at the last (highest priority) entry in the TreeMap, removes it from both structures, and returns the task ID. Time: O(log n).
Step 6: Example - addTask(1, 5), addTask(2, 3), addTask(3, 5). TreeSet has {(5,3),(5,1),(3,2)}. execTask() returns 3 (highest priority, highest ID as tiebreaker). Next execTask() returns 1.
Time: O(log n) per operation. Space: O(n) for storing all active tasks.
What Trips People Up in Real Interviews
Forgetting that two tasks can share the same priority. Use a tiebreaker (e.g. task ID) to ensure deterministic ordering in the heap or set.
Trying to remove a task from the middle of a heap in O(n) and thinking that is fine. Lazy deletion with a validity map keeps O(log n) amortized.
Not handling the case where exec() is called on a nonexistent or already-executed task. Clarify error behavior with the interviewer.
Using a simple array for the task list without any ordering structure, then claiming get() is O(1). It requires O(n) without a sorted structure.
Overcomplicating with two separate heaps instead of a single sorted set or a heap plus HashMap combo.
Solution Code
from sortedcontainers import SortedList
class TaskManager:
def __init__(self):
self.tasks = {}
self.sorted = SortedList()
def add(self, taskId: int, priority: int) -> None:
self.tasks[taskId] = priority
self.sorted.add((-priority, -taskId))
def edit(self, taskId: int, newPriority: int) -> None:
old = self.tasks[taskId]
self.sorted.remove((-old, -taskId))
self.tasks[taskId] = newPriority
self.sorted.add((-newPriority, -taskId))
def rmTask(self, taskId: int) -> None:
old = self.tasks.pop(taskId)
self.sorted.remove((-old, -taskId))
def execTask(self) -> int:
p, t = self.sorted.pop()
del self.tasks[-t]
return -tFrequently Asked Questions
What is the Design Task Manager problem?
Design a task manager system that supports adding, executing, and removing tasks with priorities, and querying the highest-priority task efficiently.
How do you solve Design Task Manager?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Design Task Manager?
Design Task Manager is asked at Apple. It is a medium difficulty problem.
What are common mistakes on Design Task Manager?
- Forgetting that two tasks can share the same priority. Use a tiebreaker (e.g. task ID) to ensure deterministic ordering in the heap or set.
- Trying to remove a task from the middle of a heap in `O(n)` and thinking that is fine. Lazy deletion with a validity map keeps `O(log n)` amortized.
- Not handling the case where exec() is called on a nonexistent or already-executed task. Clarify error behavior with the interviewer.
- Using a simple array for the task list without any ordering structure, then claiming get() is `O(1)`. It requires `O(n)` without a sorted structure.
- Overcomplicating with two separate heaps instead of a single sorted set or a heap plus HashMap combo.