Task Scheduler
medium · fake clock, priority by due time
Brief-reported interview attribution (unverified): Amazon, Microsoft
How to approach an LLD roundRequirements
- 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 orderRules. 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
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter