Task Scheduler

medium · fake clock, priority by due time

Brief-reported interview attribution (unverified): Amazon, Microsoft

How to approach an LLD round

Requirements

  • Functional: schedule a task to run after a delay, cancel it, run all due tasks in due-time order (insertion order on ties), list pending tasks.
  • Non-functional: re-scheduling an id replaces the old task; the clock is injected so the schedule is deterministic in tests.
  • Out of scope: cron expressions, retries, persistence.

Statement

Design a one-shot task scheduler. schedule(task_id, fn, delay_seconds) runs fn after delay_seconds from now (a callable with no arguments). Time comes from a clock callable passed to the constructor (default: time.time). run_due() runs every task whose time has come, in due-time order (ties in insertion order), and returns the list of task ids it ran. Scheduling an id that is already pending replaces it (new function and new time).

class TaskScheduler:
    def __init__(self, clock=None):
    def schedule(self, task_id, fn, delay_seconds):
    def cancel(self, task_id):
        # -> True if a pending task was cancelled, False otherwise
    def pending(self):
        # -> [(task_id, run_at), ...] sorted by run time (insertion order on ties)
    def run_due(self):
        # -> [task_id, ...] of the tasks that just ran, in run order

Rules. A task runs when clock() >= run_at. run_due() removes a task before calling its function (a task that re-schedules itself is a new task). pending times are absolute clock values.

Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.

Class design (SOLID)

Task (id, run time, function, insertion order; SRP). TaskScheduler holds tasks in a dict plus a min-heap of (run_at, seq, id); cancelled/re-scheduled entries stay in the heap and are skipped lazily when they surface, and run_due collects the due tasks before running any of them (so a task that re-schedules itself waits for the next call). No pattern is forced; the split (task vs scheduler) is the point.

Public demo

# Public demo: run after implementing the class API above.
now = [1000.0]
log = []
s = TaskScheduler(clock=lambda: now[0])
s.schedule('a', lambda: log.append('a'), 10)
s.schedule('b', lambda: log.append('b'), 5)
s.schedule('c', lambda: log.append('c'), 5)
print(s.run_due())
print(log)

Reference solution and hidden tests

Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.

Concurrency

Tasks run on a timer thread while new ones are scheduled: the task map must not change while run_due iterates it. Guard schedule/cancel/run_due with one lock, and run the due tasks' functions outside the lock (so a slow task does not block scheduling). The reference is single-threaded; the lock is described here.

Trade-offs & extensions

Due tasks come from the heap in O(K log H) for K popped records, including cancelled/replaced records, where H is the heap size; pending still sorts the live tasks (O(N log N)). Extending: a TaskStore for persistence.

Starter code

import heapq
import time

class Task:

    def __init__(self, task_id, run_at, fn, seq):
        """Initialize the state described in the problem."""
        pass

    def run(self):
        """Implement the return value and rules in the API contract."""
        pass

class TaskScheduler:

    def __init__(self, clock=None):
        """Initialize the state described in the problem."""
        pass

    def schedule(self, task_id, fn, delay_seconds):
        """Implement the return value and rules in the API contract."""
        pass

    def cancel(self, task_id):
        """-> True if a pending task was cancelled, False otherwise"""
        pass

    def pending(self):
        """-> [(task_id, run_at), ...] sorted by run time (insertion order on ties)"""
        pass

    def run_due(self):
        """-> [task_id, ...] of the tasks that just ran, in run order"""
        pass
Loading editor…

Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.

Return to the Python interpreter

4 comments

Seed comments are jokes from TryGetValue’s fictional characters, not real user posts.

Your posts stay in this browser, for this problem only. They are not shared with other visitors.

  1. Me at 2amCharacter joke · No posting date

    I renamed the function and everything broke. The function was load-bearing.

  2. AntyCharacter joke · No posting date

    I asked the hash for one shard. It gave me a lecture on consistency.

  3. AntyCharacter joke · No posting date

    I carried this test case uphill both ways. It still failed.

  4. InterviewerCharacter joke · No posting date

    Great approach. Now solve it without using the thing you just used.