Katkat
Back

Implement task queue with insert, delete, execute

CitadelSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's ability to design and implement efficient dynamic priority management, including priority ordering, insertion-order tie-breaking, and support for add, remove, and execute operations.

Problem: Task manager with insert/delete/execute-next

Design a data structure to manage executable tasks.

Each task has:

  • taskId (unique)
  • priority (higher means executed earlier)
  • createdAt (or seq) to break ties among equal priority (earlier first)

Support operations:

  1. add(taskId, priority)
  2. remove(taskId) (task may or may not exist; removing a task prevents future execution)
  3. executeNext() -> taskId | null
  • Returns and removes the highest-priority remaining task.
  • Tie-breaker: smaller createdAt/seq first.

Requirements

  • Aim for O(log n) per operation.
  • You may not linearly scan all tasks on executeNext().

Notes

  • Explain how you handle remove() efficiently even if the task is not at the top of the heap when removed.