How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Tesla.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Tesla during technical interviews.

Implement a Timed Task Scheduler | Tesla Coding Question

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.

Input: [(0, 1, 5, 1), (1, 2, 5, 1), (0, 3, 5, 1)]

Expected Output: [(1, 5, 6), (3, 6, 7), (2, 7, 8)]

Explanation: All tasks are ready at time 5 with the same scheduled_time. Ties are broken by smaller add_time, then by original input order.

Input: [(5, 4, 8, 2), (0, 1, 3, 1), (2, 2, 10, 1), (1, 3, 3, 2)]

Expected Output: [(1, 3, 4), (3, 4, 6), (4, 8, 10), (2, 10, 11)]

Explanation: Tasks 1 and 3 are both ready at time 3, so they run first in tie-break order. The scheduler then waits until time 8 for task 4, and finally runs task 2 at time 10.

Input: []

Expected Output: []

Explanation: With no tasks, nothing is executed.

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)`.

Quick Overview

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.