Katkat
Back

Implement a single-thread task scheduler API

Applied IntuitionSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design a priority-based scheduler using a min-heap to manage tasks triggered by relative or absolute timestamps, ensuring execution occurs in the correct temporal order.

Task Scheduler API

Design a task scheduler for a single-threaded environment that manages and executes delayed or periodic tasks. Your scheduler should support the following operations:

  1. schedule(callback, delay_ms): Schedules a function callback to be executed after delay_ms milliseconds from the current time.
  2. run(): The main loop of the scheduler. It should process all pending tasks at the appropriate times. This method should block until there are no more tasks remaining in the queue.

Requirements

  • Tasks must be executed in chronological order.
  • If multiple tasks are scheduled for the same time, their relative execution order does not matter.
  • You may assume access to a helper function get_current_time() which returns the current system time in milliseconds.
  • The run() loop should be efficient; it should not busy-wait if there is a significant gap between the current time and the next scheduled task.

Implementation Template

class TaskScheduler:
    def __init__(self):
        # Initialize data structures here
        pass

    def schedule(self, callback, delay_ms):
        # Add task to the scheduler
        pass

    def run(self):
        # Execute tasks as they come due
        pass

Example

scheduler = TaskScheduler()
scheduler.schedule(lambda: print("Task 2"), 200)
scheduler.schedule(lambda: print("Task 1"), 100)
scheduler.run()
# Output:
# Task 1
# Task 2

Constraints

  • delay_ms will be a non-negative integer.
  • The scheduler should handle a high volume of scheduled tasks.
  • Consider how to handle the time between tasks (e.g., using sleep or equivalent).

Hints

Hint 1

Use a min-priority queue (min-heap) to store tasks, where the priority is the absolute timestamp at which the task should execute.

Hint 2

The scheduler's loop should calculate the difference between the next task's execution time and the current time to determine how long to sleep.

Hint 3

If the queue is empty, the scheduler should exit the loop to prevent an infinite block.

Follow-up questions

  • How would you modify your implementation to support periodic tasks (e.g., repeating every X milliseconds)?
  • What changes are needed if the scheduler needs to be thread-safe to support concurrent calls to `schedule()`?
  • How would you handle a scenario where a task takes longer to execute than the interval until the next scheduled task?