call(back)
Algorithms & Data StructuresmediumSign in to star problems

Design Task Manager

Design a task manager over tasks that carry (userId, taskId, priority). Task ids are unique.

  • TaskManager(tasks) — initialise with a list of [userId, taskId, priority] triples.
  • add(userId, taskId, priority) — add a new task.
  • edit(taskId, newPriority) — change an existing task's priority.
  • rmv(taskId) — remove an existing task.
  • execTop() — run and remove the highest-priority task, breaking ties by the larger task id, and return its userId; return -1 when no task is left.
tm = TaskManager([[1, 101, 10], [2, 102, 20], [3, 103, 15]])
tm.add(4, 104, 5)
tm.edit(102, 8)
tm.execTop()   ->  3      // task 103 (priority 15) runs
tm.rmv(101)
tm.add(5, 105, 15)
tm.execTop()   ->  5      // task 105 (priority 15) runs

Hints

Hint 1

Keep an authoritative map from taskId to (userId, priority) alongside a max-heap ordered by (priority, taskId). add and edit push a fresh heap entry; rmv only touches the map.

Hint 2

execTop pops until the entry agrees with the map — same task present, same priority — then removes it from the map and returns the user. Entries that disagree are stale leftovers of edits and removals; discard them.

Asked at

Apple