← Applied Intuition Interview InsightsSoftware Engineer

Applied Intuition·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say
May 2026

Summary

Applied Intuition systems design round, single question but it went pretty deep. They wanted a working task scheduler design with real API definitions and a discussion of the internals. Not a vibe check, they actually pushed on edge cases.

Questions Asked (1)

Q1

Design a single-CPU, single-threaded task scheduler with APIs for one-time scheduling at an absolute time, one-time scheduling after a delay, and periodic scheduling at a fixed interval. Walk through your data structure choice, how the core loop sleeps until the next task, and how you handle clock drift, late wake-ups, and cancellation.

System DesignAlgorithms & Data StructuresTechnical Trade-offs
Author's notes

I jumped straight to the min-heap and felt pretty good about that part.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a min-heap (priority queue) keyed by absolute wake-up time as the core data structure. Walk through the scheduler loop that sleeps until the next task's deadline, and systematically address edge cases like clock drift, late wake-ups, and cancellation with concrete strategies.

Pro tip: Emphasize that a single-threaded scheduler must never block on task execution—tasks should be dispatched to a worker pool or run asynchronously, otherwise the scheduler cannot maintain timing guarantees. Also, mention using a monotonic clock for delays and intervals to avoid wall-clock adjustments.

1. Clarify Requirements and Assumptions

Ask about task duration, concurrency needs, precision requirements, and whether tasks can be cancelled. State assumptions like tasks are short-lived or dispatched to workers, and that the scheduler runs on a single thread.

2. Choose Data Structure and APIs

Propose a min-heap (priority queue) ordered by absolute execution time, supporting O(log n) insert and O(1) peek. Define APIs: schedule_at(absolute_time, task), schedule_after(delay, task), schedule_every(interval, task), and cancel(task_id).

3. Design the Core Loop

Describe the loop: peek the earliest task, compute sleep duration = max(0, next_time - now), sleep until then (using a monotonic clock), then pop and execute all tasks whose time <= now. Use a condition variable or timed wait to allow cancellation to wake the loop.

4. Handle Edge Cases

Address clock drift by using a monotonic clock for delays/intervals; handle late wake-ups by executing overdue tasks immediately and rescheduling periodic tasks based on original schedule or now (depending on policy); implement cancellation via a flag or lazy deletion with a cancelled set.

5. Discuss Trade-offs and Scalability

Compare min-heap with alternatives like timing wheels for many tasks, discuss precision vs. overhead, and mention how to avoid busy-waiting. Note that single-threaded design simplifies synchronization but may bottleneck if tasks are long-running.

Key Points to Mention

  • Min-heap (priority queue) keyed by absolute time for O(log n) insertion and O(1) peek
  • Use of monotonic clock (e.g., clock_gettime(CLOCK_MONOTONIC)) to avoid wall-clock drift
  • Sleeping via condition variable with timed wait to allow cancellation to interrupt sleep
  • Handling late wake-ups: execute overdue tasks immediately; for periodic tasks, decide whether to skip missed intervals or catch up
  • Cancellation strategies: lazy deletion with a cancelled set or direct removal from heap (O(n) but acceptable for small n)
  • Trade-offs: min-heap vs. timing wheel for large numbers of tasks; single-threaded simplicity vs. potential blocking

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.