Implement a Timed Task Scheduler
Company: Tesla
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a runnable task scheduler.
The scheduler should allow clients to add new tasks at any time. Each task has:
- A callback or function to execute.
- A scheduled execution time, such as a timestamp or delay.
Requirements:
1. A task must execute no earlier than its scheduled time.
2. The scheduler should keep running and execute tasks as they become due.
3. Clients may add tasks while the scheduler is already running.
4. If multiple tasks are scheduled, they should be executed in increasing order of scheduled time.
5. Provide a small runnable example or test showing tasks being added and executed at the expected times.
You may choose the programming language, but your implementation should be clear, correct, and runnable.
Quick Answer: This question evaluates a candidate's ability to implement timed task scheduling, encompassing time-based ordering, task execution semantics, concurrency control, and synchronization for runnable tasks.
Implement a single-threaded timed task scheduler as a simulation.
Each task is given as a tuple `(add_time, task_id, scheduled_time, duration)`:
- `add_time`: the time when a client adds the task to the scheduler
- `task_id`: an integer identifying the task's callback
- `scheduled_time`: the earliest time the task is allowed to start
- `duration`: how long the task runs once started
The scheduler runs continuously and may receive new tasks while another task is already running.
Scheduling rules:
1. A task cannot start before both its `add_time` and its `scheduled_time`.
2. The scheduler is single-threaded, so only one task can run at a time.
3. Whenever the scheduler chooses the next task, it must select the READY task with the smallest `scheduled_time`.
4. If multiple ready tasks have the same `scheduled_time`, choose the one with the smaller `add_time` first.
5. If there is still a tie, preserve the original input order.
6. If no task is ready, the scheduler waits until the next task becomes ready.
Return the execution log as a list of tuples `(task_id, start_time, finish_time)` in the order tasks are executed.
Note: In a real system each task would contain a callback function. For this problem, the callback is represented only by `task_id`, and you only need to simulate the scheduler.
Constraints
- 0 <= len(tasks) <= 200000
- 0 <= add_time, scheduled_time <= 10^9
- 1 <= duration <= 10^9
- Each task_id is an integer
- All computed times fit in a signed 64-bit integer
Examples
Input: [(0, 101, 5, 3), (2, 102, 4, 2), (6, 103, 6, 1)]
Expected Output: [(102, 4, 6), (101, 6, 9), (103, 9, 10)]
Explanation: Task 102 becomes ready at time 4 and runs first from 4 to 6. By time 6, tasks 101 and 103 are ready; 101 has the earlier scheduled_time, so it runs next, then 103.
Input: [(0, 1, 2, 5), (3, 2, 1, 2), (4, 3, 4, 1)]
Expected Output: [(1, 2, 7), (2, 7, 9), (3, 9, 10)]
Explanation: Task 1 starts at time 2 and blocks the scheduler until 7. Task 2 was added late but is already overdue when added, so it is ready from time 3 and has the smallest scheduled_time among ready tasks when the scheduler becomes free.
Hints
- A task becomes ready at time `max(add_time, scheduled_time)`.
- Sort tasks by ready time, then use a min-heap for the ready queue ordered by `(scheduled_time, add_time, original_index)`.