PPractick

The problem

An operating-systems course simulates a CPU scheduler. n processes all arrive at time 0 with known burst times, and the CPU runs them one at a time, without preemption. A process's waiting time is how long it sits in the queue before starting. Which order minimises the average waiting time, and what is it (rounded down)? Shortest Job First: run the shortest jobs first. Each job's burst delays every job after it, so short jobs should go first.

Example: bursts [4, 3, 7, 1, 2] → 4 (order 1, 2, 3, 4, 7 gives waits 0, 1, 3, 6, 10).

Function signature

long long averageWaitingTime(vector<int> bt);  // floor of the average waiting time

Test cases

Input	Output	Explanation
[4, 3, 7, 1, 2]	4	Total wait 20, divided by 5
[1, 2, 3, 4]	2	10 / 4 = 2.5, rounded down
[2, 2, 2]	2	Waits 0, 2, 4
[10, 1]	0	Waits 0, 1: average 0.5
[5]	0

(Confirm: all processes arrive at time 0; non-preemptive; the result is the floor of the average.)

How interviewers phrase it

• "Given burst times of n processes arriving at time 0, find the average waiting time using the Shortest Job First policy" (GeeksforGeeks "Shortest Job first").

Clarifying questions to ask

1. Do all processes arrive at time 0? (Yes; different arrival times need a heap-based simulation.)
2. Preemptive or not? (Non-preemptive.)
3. How should the average be rounded? (Floor.)

Follow-ups to expect

1. "Why is SJF optimal for total waiting time?"
2. "What if processes arrive at different times?"
3. "Downside of SJF?"
4. "Turnaround time?"
5. "Complexity?"

Related questions

• Fractional Knapsack Medium
• N meetings in one room Medium
• Minimum number of platforms required for a railway Medium
• Job sequencing Problem Medium
• Insert Interval Medium
• Merge Intervals Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in