Coding

Shortest Job First

Asked at

Salesforce

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

A software engineer is tasked with using the shortest job first (SJF) policy to calculate the average waiting time for each process. The shortest job first also known as shortest job next (SJN) scheduling policy selects the waiting process with the least execution time to run next.

You are given an array of integers **bt **of size n representing the **burst times (execution times) **of n processes.

Your task is to calculate the average waiting time for all processes when scheduled using the SJF policy. The waiting time of a process is the total time a process has to wait before its execution starts, which is the sum of burst times of all previously executed processes.

Return the floor of the average waiting time, i.e., the largest whole number less than or equal to the actual average.

Input : bt = [4, 1, 3, 7, 2] Output : 4 Explanation : The total waiting time is 20. So the average waiting time will be 20/5 => 4.

Input : bt = [1, 2, 3, 4] Output : 2 Explanation : The total waiting time is 10. So the average waiting time will be 10/4 => 2.

Input : bt = [9, 3, 1, 8, 2]

1 <= n <= 105
1 <= bt[i] <= 105

cpp

class Solution {
  public:
    long long solve(vector<int>& bt) {
        //your code goes here
    }
};

java

class Solution {
    public long solve(int[] bt) {
        //your code goes here
    }
}

python

class Solution:
    def solve(self, bt):
        #your code goes here

javascript

class Solution {
    solve(bt) {
        //your code goes here
    }
}

csharp

public class Solution
{
    public long Solve(List<int> bt)
    {
        //your code goes here
    }
}

func solve(bt []int) int64 {
	//your code goes here
}

Stuck? Show a way to structure it+

01Clarify preemptive versus non-preemptive and arrival assumptions
02Sort durations if all arrive together
03Accumulate elapsed time and waiting-time total
04For arrivals, push available jobs into a min-heap

Reference answer

Start by restating the input contract for Shortest Job First and testing the smallest boundary case before choosing the algorithm. For non-preemptive SJF with all jobs arriving at time zero, sort burst durations ascending and accumulate waiting times: each job waits for the total duration before it. If arrival times vary, use a min-heap of available jobs while advancing time. Explain the invariant while coding, then show how each update preserves it. Sorting the jobs costs O(n log n) time and the accumulation is O(n); with in-place sorting, auxiliary space is O(1). Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

How does shortest remaining time first differ?
Tests: complexity analysis
Can starvation occur?
Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question