venkatesh
№055 · OCT 08, 2026 · 3 MIN READ

Interviewer: Build a Task Scheduler

A queue, then a PriorityQueue, then a mistake: remove() on a heap is O(n).
careersystem-design

Interviewer: “Build a task scheduler.”

Simple enough.

Requirements are simple:

  1. add a task
  2. execute a task

Run tasks in order. First come, first served. I used a queue.

Follow-up: “tasks have a priority now”

Switched to a PriorityQueue sorted by priority. Every insertion now takes O(log n).

Follow-up: “users can remove or modify tasks”

I thought of lazy deletion using the PriorityQueue.

remove() on a PriorityQueue is O(n). It scans the whole heap to find one task.

That was the mistake 💀

“Can we optimize it more?”

I thought for a few minutes and came up with an indexed priority queue + map. But that’s overkill for this use case.

Finally he hinted TreeSet.

Add, remove, modify, pick next task: all O(log n).

But TreeSet brings its own problems:

  • two tasks with the same priority means compare() returns 0, so one task is silently dropped
  • so you need a tiebreaker: priority, then createdAt, then taskId

The trade-off

  • Removes are rare → PriorityQueue works fine.
  • Removes are frequent → TreeSet.

Asking all the functional requirements before writing the first line was important.

Finding the data structure is the second problem.

copied!