p90 — Single-Threaded CPU

Source: LeetCode 1834 · Medium · Topics: Heap, Simulation, Sorting Companies (2024–2025): Amazon (high), Google (medium), Microsoft (medium), Bloomberg (medium) Loop position: Discrete-event simulation with a ready-queue heap. Combines sort-by-enqueue + min-heap of (proc_time, idx) tie-break + time fast-forward when idle.

1. Quick Context

Given tasks[i] = [enqueueTime, processingTime], simulate a CPU:

  • Idle CPU picks the shortest-processing-time task that has arrived (tie-break: smallest index).
  • Return the order tasks are processed.

Algorithm:

  1. Sort tasks by enqueueTime keeping original index.
  2. Walk a pointer + maintain cur_time + min-heap of (proc_time, idx) for ready tasks.
  3. Each iteration:
    • If heap empty, fast-forward cur_time to next task’s enqueue.
    • Push all tasks with enqueueTime ≤ cur_time.
    • Pop heap; append idx to order; cur_time += proc_time.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/single-threaded-cpu/

STOP. 30-min timer.

3. Prerequisite Concepts

  • Discrete-event simulation.
  • Two-pointer over sorted events.
  • Heap tie-break by lexicographic tuple.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Simulate SJF (shortest job first) on a single CPU, breaking ties by original index.

2. Clarify: Insertion order in heap = arrival order? Yes via (proc_time, idx) tuple.

3. Examples: tasks = [[1,2],[2,4],[3,2],[4,1]] → time 1 push idx0; pop (2,0); time 3 push 1,2; pop (2,2); time 5 push 3; pop (4,1); push (1,3) earlier; … result: [0,2,3,1].

5. Brute: Same simulation with naive O(n²) ready-set scan.

6. Target: O(n log n).

7. Pattern: Sort + heap + fast-forward.

8. Develop: see solution.py.

9. Test: all enqueue at 0; single task; large gap between enqueues.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 Why sort by enqueue?

Tasks arrive over time. Pointer walks through enqueue-sorted list; everything before the pointer with enqueue ≤ cur_time is in the heap. Sort makes this O(n) over all iterations.

6.2 The fast-forward step

When the CPU is idle and heap is empty, time jumps to the next task’s enqueue time. Don’t simulate every clock tick — costly and unnecessary.

Specifically: cur_time = max(cur_time, tasks[ptr].enqueue).

6.3 Tie-break correctness

Python’s tuple comparison compares element-wise. (proc_time, original_idx) ensures:

  • Shorter proc_time wins.
  • On tie, smaller original_idx wins.

6.4 Why min-heap, not other structures?

  • Sorted set / BST works but heavier.
  • Min-heap is the natural fit for “pop the smallest-priority element repeatedly”.
  • Average O(log n) per push/pop.

6.5 SJF vs FIFO vs round-robin

This is Shortest Job First (SJF) with non-preemptive policy. SJF minimizes average wait time for known job sizes. Real OS schedulers use approximations (multilevel feedback queues) since job size is unknown.

6.6 Family: discrete-event simulation with priority queue

  • LC 1834 Single-Threaded CPU (this).
  • LC 1882 Process Tasks Using Servers (two-heap: free servers + busy servers).
  • LC 1942 Number of Smallest Unoccupied Chair (similar pattern).
  • LC 502 IPO (two-heap with gating).
  • LC 295 Find Median from Data Stream (two-heap for medians).

7. Anti-Pattern Analysis

  1. Use just one queue (FIFO) — produces wrong order; not SJF.
  2. Sort by processingTime initially — destroys enqueue ordering; lookups become quadratic.
  3. Iterate per clock tick — O(maxTime) blow-up.
  4. Forget tie-break by idx — heap pops in proc_time order but unstable on ties.
  5. Push all tasks into heap upfront — picks tasks before they “arrive”.
  6. Use tasks.pop(0) from sorted list — O(n) per pop = O(n²) total.

8. Skills & Takeaways

  • Discrete-event simulation pattern.
  • Heap with tuple tie-break.
  • Fast-forward when idle.

9. When to Move On

  • Solve cold in 20 min.
  • Articulate the fast-forward and tuple tie-break.
  • Cite LC 1882 servers as the next step.

10. Company Context

  • Amazon: L4/L5; very common phone screen.
  • Google: L5.
  • Microsoft: L5; OS-flavored.
  • Bloomberg: common.

Strong: “Sort by enqueue + min-heap of (proc_time, idx); fast-forward when idle; cited LC 1882 servers as the two-heap generalization.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
Heap patternAfter hintColdClean+ fast-forward proof
Tie-breakMissesAfter testCold+ tuple comparison reasoning
FamilyNoneNoneLC 1882+ LC 295 median + LC 502 IPO
EdgeForgets idleTime jumpCold+ bounded

12. Level Delta

  • Mid (L4): Heap + sort, may miss fast-forward.
  • Senior (L5): Cold; tuple tie-break correct; fast-forward.
  • Staff (L6): + cites SJF/EDF connection; + multi-server generalization.
  • Principal (L7+): + framing as non-preemptive SJF optimality for total wait time + LP analog + connection to OS schedulers (CFS, MLFQ).

13. Follow-up Q&A

Q1: Multi-CPU? A1: LC 1882: two heaps (free servers min-heap by weight+idx; busy servers min-heap by free_time). Standard generalization.

Q2: Preemptive (interruptible task)? A2: Preemptive SJF (SRTF — Shortest Remaining Time First) — heap of remaining-time; on each new arrival, compare against currently-running.

Q3: Tasks have priorities, not just sizes. A3: Replace (proc_time, idx) with (priority, proc_time, idx).

Q4: Tasks can be batched (parallel up to k). A4: Becomes flow-shop / open-shop; NP-hard for k ≥ 2 with arbitrary processing times.

Q5: What’s the avg wait time under this algorithm? A5: SJF is provably optimal for minimizing average wait time when sizes are known a priori.

14. Solution Walkthrough

See solution.py:

  • get_order — sort + heap + fast-forward.
  • get_order_brute — O(n²) simulation oracle.

15. Beyond the Problem

Principal code review: “Single-Threaded CPU is SJF (Shortest Job First) non-preemptive in textbook form. The Staff+ insight is that SJF is provably optimal for minimizing average waiting time when job sizes are known — a foundational result in scheduling theory (Smith’s rule, 1956). Real OS schedulers can’t use SJF directly because job sizes are unknown; instead they approximate via Multi-Level Feedback Queues (MLFQ) and Completely Fair Scheduler (CFS, Linux) which use aging to approximate SJF without prior knowledge. The lesson scales: discrete-event simulation with a priority queue is the workhorse for any ‘simulate this system’ interview question, and the structure is always: (1) sort events by time, (2) maintain a heap of currently-ready entities, (3) pop in priority order, (4) fast-forward time when idle. This pattern appears in ad-auction simulators, packet routing simulators, financial-trading match engines (Bloomberg loves this), and game-engine event loops. Once you internalize the four steps, every simulation problem collapses to filling in the priority key and the state update.”