Katkat
Back

Design a Priority Task Executor with Duplicate Task IDs

SnowflakeSoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This problem tests your ability to design a thread-safe task scheduler that handles duplicate task IDs while ensuring each unique task is executed exactly once based on priority and submission time.

Design a Priority Task Executor

Design an in-memory class TaskExecutor that manages task execution based on priority. Each task is represented by a unique taskId and an associated priority. A task may be submitted multiple times with the same taskId, potentially with different priorities or timestamps. However, each unique taskId must be executed exactly once.

Requirements

  1. addTask(taskId, priority, timestamp): Adds a task to the queue. If a taskId is submitted multiple times, the executor should track the most recent priority and timestamp for that ID.
  2. executeTask(): Removes and returns the taskId that should be executed next. The execution order is determined by:
    • Higher priority first.
    • If priorities are tied, the task with the earliest timestamp is executed first.
    • If a taskId has already been executed, it must be ignored/skipped.

Interface

class TaskExecutor:
    def addTask(self, taskId: int, priority: int, timestamp: int) -> None:
        pass

    def executeTask(self) -> Optional[int]:
        pass

Examples

Example 1:

  • addTask(1, 10, 100)
  • addTask(2, 20, 50)
  • addTask(1, 15, 120)
  • executeTask() -> Returns 2 (Highest priority 20).
  • executeTask() -> Returns 1 (Highest priority 15, updated from previous submission).

Constraints

  • Number of operations: 10^5.
  • Priorities and timestamps are integers.
  • The solution must be thread-safe for concurrent calls.

Considerations

  • How will you handle efficient lookups to check if a task has already been executed?
  • How do you update an existing task's priority without scanning the entire queue?
  • How can you ensure the thread safety of both the priority storage and the execution state?

Hints

Hint 1

Use a hash map to store the current 'best' priority and timestamp for each taskId, and a separate set to track IDs that have already been executed.

Hint 2

Use a Min-Heap (or Max-Heap) to store the tasks, but since you cannot easily update priorities in a standard heap, consider using 'lazy removal' where you store all task entries in the heap and skip them if they are stale or already executed.

Hint 3

To ensure thread safety, wrap the internal data structures (the map, the set, and the heap) using a reentrant lock or a concurrent dictionary/priority queue.

Follow-up questions

  • How would you modify the system if we needed to support a 'cancelTask(taskId)' operation?
  • If the system crashes, how would you persist the state of executed tasks to ensure no taskId is executed twice upon restart?
  • If the number of `addTask` operations is significantly higher than `executeTask`, how could you optimize the `addTask` latency?