Single-Threaded CPU

Single-Threaded CPU

What is this problem about?

The "Single-Threaded CPU" interview question is a complex simulation problem that mimics how an operating system's scheduler might work. You are given a list of tasks, each with an enqueue time and a processing time. A single-threaded CPU can only process one task at a time. If the CPU is idle, it picks the task with the shortest processing time from the available pool. If two tasks have the same processing time, it picks the one with the smaller original index. This "Single-Threaded CPU coding problem" requires carefully managing the flow of time and the pool of available tasks.

Why is this asked in interviews?

Companies like Goldman Sachs and Microsoft ask this to evaluate a candidate's ability to handle complex state and multiple data structures simultaneously. It tests your proficiency with priority queues (heaps) and sorting. The problem requires you to think about event-driven simulation—how to efficiently jump between timestamps when the CPU is idle versus when it is busy.

Algorithmic pattern used

This problem is a classic application of the "Sorting and Heap (Priority Queue) interview pattern".

1. Sort all tasks by their enqueue time.
2. Use a min-heap to store "available" tasks. Each entry in the heap should be (processing_time, original_index).
3. Keep track of current time.
4. While there are tasks to process:
   • If the heap is empty and the next task hasn't arrived yet, jump the current time to the next task's enqueue time.
   • Add all tasks that have arrived by the current time into the heap.
   • Pick the best task from the heap, update the current time by its processing time, and record its index.

Example explanation

Tasks: T0: (1, 2), T1: (2, 4), T2: (3, 2) (format: (enqueue, processing))

1. Time 0: No tasks. Next task T0 arrives at time 1.
2. Time 1: T0 arrives. Add T0 to heap. Heap: [(2, 0)].
3. CPU picks T0. Time becomes 1 + 2 = 3.
4. Check for arrived tasks: T1 and T2 have arrived. Add to heap. Heap: [(4, 1), (2, 2)].
5. Min-heap picks the shortest task: T2 (processing time 2). Time becomes 3 + 2 = 5.
6. CPU picks T1. Time becomes 5 + 4 = 9. Order: [0, 2, 1].

Common mistakes candidates make

One major pitfall is not handling the "idle CPU" case correctly, where no tasks are available in the heap but more tasks will arrive later. Another common mistake is failing to include the original index in the heap, which is necessary to break ties. Candidates also sometimes struggle with the logic of adding all eligible tasks to the heap before picking the next one to process.

Interview preparation tip

Mastering the Priority Queue is essential for any "Single-Threaded CPU interview question". Remember that heaps are perfect for "find the minimum among currently available options" scenarios. Also, when sorting tasks that have multiple properties, always keep their original index if the problem requires it for output or tie-breaking.