Cron Scheduler
Track: Load and timing. 7 stages. Languages: Go, Python, Rust.
Cron is the classic tool for running a job again and again on a fixed schedule, like "every 15 minutes" or "every Monday at 9am". You will build two things: a calculator that works out when a schedule should fire next, and a real scheduler that waits and fires jobs on time.
A schedule is written as 5 fields: minute, hour, day of the month, month, day of the week. Each field is (any), a number, a range (a-b), a list (a,b,c), or a step (/n). Day of the week runs 0-6, Sunday is 0. A couple of examples: /15 * * fires every 15 minutes, at :00, :15, :30, and :45 of every hour. 0 9 * 1 fires at 9:00 every Monday.
Build New(), Next(spec, after) -> time (works out the next fire time, a pure calculation with no waiting), Schedule(id, everyMs, job), Cancel(id), and Run(ctx) (the part that actually waits and fires jobs).
Most stages below use short waits, well under a second, so a test finishes quickly. Your code doesn't change for that: it just waits for real, shorter amounts of time. One stage (cs7) runs on our servers with a clock that skips idle waiting, so an hour of schedule checks in seconds. Your code still doesn't change: it just experiences time moving fast while it is waiting.
Standard library only. For help with the ideas, read the notes.
Where it is used
- Unix and Linux machines run
cron, which reads a list of 5-field schedules and runs a command each time one matches: backups, log cleanup, reports. - Kubernetes CronJobs use the same 5-field format to start jobs in a cluster. If a run is missed by too much, they can skip it instead of starting it late.
- systemd timers can do the opposite: with
Persistent=true, a run that was missed while the machine was off happens right after it starts again.
A scheduler that runs every missed tick at once after a pause can start the same backup ten times in a row.
Stages
cs1: the next time for an everyday schedule (easy)
Work out the next fire time after a given moment, for everyday schedules: every N minutes, every hour, every day, a weekday, a day of the month, and an hour range. Example: /15 * * after 10:07 gives 10:15. 0 9 * 1 (every Monday at 9:00) gives the next Monday at 9:00, even if that is several days away.
The tester will verify: your answer for 6 everyday schedules matches our solution, including minute and hour rollovers.
cs2: the harder schedules: both day fields, leap years, short months (medium)
Handle the trickier cases. If a schedule limits both the day of the month and the day of the week, a day counts if either one matches, not only if both do. Also handle February 29 landing on the next leap year, and the 31st skipping months that don't have one. Example: 0 0 13 * 5 means the 13th of the month OR any Friday, whichever comes first, not only Friday the 13th.
The tester will verify: your answer for 6 schedules matches our solution, including the either-day rule, the leap year jump, and short months being skipped.
cs3: fire on a steady schedule (medium)
Build a schedule that fires every 30 ms over a 1.2 second window, so it should fire about 40 times. Each fire does a small bit of simulated work before returning.
The tester will verify: the fire count over the window falls between 28 and 55. (A loop that waits the full period again only after each job finishes falls behind and fires too few times.)
cs4: skip missed ticks, and stop on cancel (hard)
Two checks on the same every-30ms schedule. First: when one fire is slowed down on purpose, your schedule must skip the ticks it missed, not fire a burst of catch-up jobs once it is free again. Second: once Cancel is called, no later fire should happen (a fire already in progress may still finish).
The tester will verify: at most 2 fires land very close together around the slow one, and the last fire happens no more than 45 ms after Cancel is called.
cs5: run several schedules at once (hard)
Run 4 separate schedules at the same time, each firing every 30 ms over a 1.2 second window. Each fire does 20 ms of work. Each one should keep its own pace: a busy schedule must not slow down or speed up another one. If your scheduler runs only one job at a time, the schedules wait for each other and fall behind.
The tester will verify: every one of the 4 schedules fires between 24 and 55 times.
cs7: a real five-minute schedule, checked on a fast clock (hard)
Run one schedule every 5 minutes over a full hour, with each fire doing 2 seconds of simulated work. This stage runs on a server clock that skips idle waiting, so it checks in seconds instead of an hour. To pass, your schedule must actually wait on a timer for the next tick, not check the clock in a tight loop: every time your code wakes up costs a small amount of real time, even on the fast clock, and waking up thousands of times for one hour of schedule runs out of that time.
The tester will verify: 8 to 18 fires, each one landing close to its 5-minute mark (at most one exception), and every 5-minute slot in the hour firing exactly once (at most one slot can be missing, none firing twice). Graded on our servers only. A local test run skips this stage.
cs6: make Next fast (L2, hard)
Keep Next fast even when the next match is far away, like once a week. Jump straight to the field that needs to change instead of checking every single minute in between. Example: finding next Sunday midnight from a Monday can be up to a week away. Jumping field by field costs a handful of steps. Checking minute by minute costs thousands.
The tester will verify: your Next takes at most 1.5 times as long as our solution, and every answer stays correct.
Rules
- Standard library only.
Nextis a pure function: no waiting, no side effects, compute in UTC. - Fire each tick from a fixed starting point (the moment the schedule started), not from when the last fire finished, so the schedule doesn't drift later over time.
- When a job overruns its slot, skip the ticks it missed. When
Cancelis called, stop that schedule. - Work out
Nextby jumping between fields, not by checking every minute one at a time.