Design Task Manager

Design Task Manager

What is this problem about?

The Design Task Manager coding problem asks you to build a system that manages tasks with user IDs, task IDs, and priorities. You need to support adding tasks, editing their priorities, deleting tasks, and most importantly, finding the task with the highest priority. If multiple tasks have the same priority, the one with the largest task ID should be returned.

Why is this asked in interviews?

Bloomberg and Bloomberg frequently ask this to test your ability to maintain a sorted set of data while supporting frequent updates. It evaluations your knowledge of the heap interview pattern or ordered set interview pattern. The challenge is that standard heaps don't support efficient priority updates, so you must find a way to handle "stale" data or use a more flexible structure.

Algorithmic pattern used

There are two main approaches:

1. Ordered Set (TreeSet): Store tasks as objects with a custom comparator that sorts by priority then task ID. This allows $O(\log N)$ updates, deletions, and retrievals.
2. Max-Heap with Lazy Deletion: Use a Max-Heap for execTop. Use a Hash Map to store the current state of each task. When execTop is called, pop from the heap until you find a task whose priority and existence match the Hash Map.

Example explanation

1. addTask(user=1, task=101, priority=5): Task 101 added.
2. addTask(user=2, task=102, priority=5): Task 102 added.
3. execTop(): Both have priority 5. Task 102 has a larger ID. Return User 2.
4. editPriority(101, 10): Task 101 now has priority 10.
5. execTop(): Task 101 has the highest priority. Return User 1.

Common mistakes candidates make

• Slow Update: Using a simple list and sorting it every time execTop is called ($O(N \log N)$).
• Stale Heaps: Populating a heap but failing to handle priority changes, leading to the system returning outdated priorities.
• Tie-breaking: Forgetting to incorporate the task ID into the sorting logic.

Interview preparation tip

If the language you use (like C++ or Java) has a set or TreeMap, use it! These structures are essentially balanced BSTs and are often superior to Heaps for design problems because they support $O(\log N)$ removal of any element, not just the top one.