MediumHash TableDesignHeapOrdered SetUpdated Sep 2026

3408. Design Task Manager

Asked at Apple

Difficulty

Medium

Time

O(log n) per operation

Space

O(n)

Pattern

Hash Table

Companies

1

Problem

Design a class called TaskManager that keeps track of tasks. Each task has a taskId, a priority, and a userId (the user who owns it). One user can own many tasks.

The constructor receives a list of triples [userId, taskId, priority] and loads them all as active tasks. After that, four methods must work:

  • add(userId, taskId, priority) — create a new task. The taskId is guaranteed to be new.
  • edit(taskId, newPriority) — change the priority of an existing task. The taskId is guaranteed to exist.
  • rmv(taskId) — delete an existing task. The taskId is guaranteed to exist.
  • execTop() — pick the task with the highest priority among all active tasks, remove it, and return its userId. If two tasks share the highest priority, pick the one with the larger taskId. If no tasks are left, return -1.

All operations should be fast, because there can be up to 2 * 10^5 calls in total and up to 10^5 tasks at the start.

What execTop must pick

active tasksabctaskIdpriorityuserId10110110282103153Task 103 has the highest priority (15), so it isexecuted first.
After the first three operations the active tasks are 101 (p=10), 102 (p=8) and 103 (p=15), so execTop returns user 3.

Constraints

  • ●1 <= tasks.length <= 10^5
  • ●0 <= userId <= 10^5
  • ●0 <= taskId <= 10^5
  • ●0 <= priority <= 10^9
  • ●0 <= newPriority <= 10^9
  • ●At most 2 * 10^5 calls in total to add, edit, rmv and execTop
  • ●taskId is always valid for edit and rmv, and always new for add

Examples

Example 1
Input["TaskManager", "add", "edit", "execTop", "rmv", "add", "execTop"] [[[[1, 101, 10], [2, 102, 20], [3, 103, 15]]], [4, 104, 5], [102, 8], [], [101], [5, 105, 15], []]
Output[null, null, null, 3, null, null, 5]
WhyStart with tasks 101 (p=10), 102 (p=20), 103 (p=15). add(4,104,5) creates a low-priority task. edit(102,8) drops task 102 from p=20 to p=8. Now the highest priority is 15, held by task 103, so execTop returns userId 3 and removes 103. rmv(101) deletes task 101. add(5,105,15) creates a task with prio
Example 2
Input["TaskManager", "execTop", "add", "add", "execTop", "execTop"] [[[]], [], [1, 5, 7], [2, 9, 7], [], []]
Output[null, -1, null, null, 2, 1]
WhyThe manager starts empty, so the first execTop returns -1. Then we add task 5 (p=7, user 1) and task 9 (p=7, user 2). Both have the same priority, so the tiebreaker picks the larger taskId: task 9, owned by user 2. The next execTop takes task 5, owned by user 1. After that nothing is left, so the la

Asked At

1 companies
CompanyDifficulty
AppleMediumView all Apple questions →

How to Think About It

1

Brute force: store tasks in a list, scan all tasks for every operation. Add and remove are O(n), get is O(n).

2

Use a max-heap to get the highest-priority task in O(1) but removal by task ID becomes O(n) without extra bookkeeping.

3

Combine a HashMap of task ID to priority with a TreeMap or heap for ordered access. The HashMap gives O(1) lookup by ID.

4

For removal, mark tasks as invalid in the heap lazily rather than rebuilding the heap, giving amortized O(log n) per operation.

5

A TreeSet or sorted set of (priority, taskId) pairs supports add, remove, and get-max all in O(log n).

6

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.

Hash map + ordered set

taskId -> priorityidprio101102103101101022010315Step 1 — store each task's current priority in a hashmap.sorted set (priority, taskId)(20,102)(15,103)(10,101)Step 2 — keep the same tasks in a sorted set, biggestfirst.after edit(102, 8)(15,103)(10,101)(8,102)Step 3 — edit removes the old pair and inserts the newone, so 103 is now on top.add: map[id]=p; set.add((p,id))edit: set.remove((old,id)); set.add((new,id))execTop: pop max pair, delete from map
The map gives O(1) lookup by taskId; the ordered set gives the top task in O(log n).
ComplexityTime O(log n) per operationSpace O(n)Each add, edit, rmv and execTop touches one hash-map entry and one ordered-set entry, and the ordered set costs O(log n) per change.

What Trips People Up in Real Interviews

1

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.

2

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.

3

Not handling the case where exec() is called on a nonexistent or already-executed task. Clarify error behavior with the interviewer.

4

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.

5

Overcomplicating with two separate heaps instead of a single sorted set or a heap plus HashMap combo.

Solution Code

O(log n) per operation time
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 -t

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(log n) per operation time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.