coderz.py

Problem Statement (Asked By Apple)

Design a job scheduler that accepts a function f and an integer n. The scheduler should execute the function f after a delay of n milliseconds.

Problem link: https://leetcode.com/problems/task-scheduler/description/

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

---

Solution:

We can implement a job scheduler in various ways, so it’s fine if your approach differs. Here, we’ll demonstrate one possible solution.

Initial Approach:

A straightforward way is to start a new thread for each delayed function. The thread will sleep for the specified time and then execute the function. This could look something like this:

Naive Implementation (Inefficient):

import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

public class Scheduler {

    public void delay(Runnable task, int delayInMillis) {
        new Thread(() -> {
            try {
                Thread.sleep(delayInMillis);
                task.run();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }).start();
    }

    public static void main(String[] args) {
        Scheduler scheduler = new Scheduler();
        scheduler.delay(() -> System.out.println("Task executed!"), 1000);
    }
}

While functional, this approach has a significant flaw: each call to delay creates a new thread, which could lead to excessive thread creation and resource exhaustion.

Optimized Approach: Using a Single Dedicated Thread

Instead of creating a new thread for each task, we can use a single dedicated thread to manage all scheduled tasks. We’ll store the tasks in a list along with their scheduled execution times. The thread will periodically check the list for due tasks, execute them, and remove them.

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

public class Scheduler {
    private final List<Task> tasks = new ArrayList<>();
    private final ScheduledExecutorService executor = Executors.newSingleThreadScheduledExecutor();

    public Scheduler() {
        executor.scheduleAtFixedRate(this::poll, 0, 10, TimeUnit.MILLISECONDS);
    }

    private synchronized void poll() {
        long currentTime = System.currentTimeMillis();
        List<Task> toRemove = new ArrayList<>();

        for (Task task : tasks) {
            if (task.dueTime <= currentTime) {
                task.runnable.run();
                toRemove.add(task);
            }
        }
        tasks.removeAll(toRemove);
    }

    public synchronized void delay(Runnable task, int delayInMillis) {
        tasks.add(new Task(task, System.currentTimeMillis() + delayInMillis));
    }

    private static class Task {
        Runnable runnable;
        long dueTime;

        Task(Runnable runnable, long dueTime) {
            this.runnable = runnable;
            this.dueTime = dueTime;
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Scheduler scheduler = new Scheduler();
        scheduler.delay(() -> System.out.println("Task 1 executed!"), 1000);
        scheduler.delay(() -> System.out.println("Task 2 executed!"), 2000);
    }
}

Explanation:

1. Task Management:
   • Each task is stored in a Task object, which contains the function (Runnable) and the scheduled execution time (dueTime).
2. Polling:
   • A single thread periodically checks (polls) the task list.
   • If the current time exceeds the task’s dueTime, the task is executed, and it’s removed from the list.
3. Adding Tasks:
   • New tasks are added to the list along with their execution time.

Additional Improvements:

• Use a Priority Queue:
  • Replace the List with a PriorityQueue to efficiently retrieve the next task to run.
• Condition Variables:
  • Instead of polling, use condition variables to wake up the thread when a new task is added.
• Thread Pool:
  • Use a thread pool to avoid potential starvation, allowing multiple tasks to run concurrently.

Time Complexity:

• Polling: O(n) per poll (can be improved to O(logn) with a heap).
• Adding a task: O(1) with a list, O(logn) with a heap.

Space Complexity: O(n), where n is the number of scheduled tasks.

---

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.