Machine coding · Schedulers and queues

Scheduling M jobs on N threads under four policies

Reported once
SDE-1 (experienced)
Strategy
Open-closed principle
1 source

One candidate write-up. Treat it as a single data point.

The prompt

Schedule M jobs across N threads on one machine. Each job has a name, a duration, a priority where P0 is the highest, a deadline and a submitter type (root, admin or user). Implement shortest job first, first come first served, fixed priority and earliest deadline first, with the tie-break rules the report lists, print the order of jobs on each thread, and skip a job under the deadline policy when it cannot finish in time. Expect the requirements to change once the first version works.

Restated in our own words, not a quote from Flipkart or any page. The answer below is written for this site.

Try it first.The answer is covered until you pick. Talk it through against a 60 minute clock, or just read it.

Clarify first

Pin the scope down before you name a single class.

Ask these before writing anything, because the answers change the algorithm.

Are all M jobs known up front, or do they arrive over time? Assume all are ready at time 0, and input order is arrival order.
Can a running job be pre-empted? Assume no: a job runs to completion on one thread.
Is the deadline an absolute time on the same clock that starts at 0? Assume yes, and durations are whole time units.
How are ties broken? The report lists rules: shortest job first prefers higher priority; fixed priority prefers the higher submitter rank (root, then admin, then user) and then the longer job; earliest deadline prefers higher priority and then the shorter job. Assume those, and input order after them.
Do you run real threads or print the plan? Assume the plan is the output and a thin executor could run it.

Out of scope: pre-emption, dependencies between jobs, jobs that arrive while others run.

Entities and relationships

Who owns what, and who talks to whom.

Job is validated input: name, duration, priority (P0 is 0), deadline and submitter type with its rank, plus its input index for first come first served and tie-breaking.
SchedulingPolicy is the strategy interface with two methods: compare(a, b) decides the order and canRun(job, start) decides whether the job may start at that time. FcfsPolicy, ShortestJobFirstPolicy, FixedPriorityPolicy and EarliestDeadlinePolicy implement it, and LongestJobFirstPolicy is the extension added without touching the scheduler.
ThreadSlot is one thread: the time it becomes free and the runs placed on it.
JobScheduler has N thread slots and one policy, and turns a list of jobs into a result with the thread timelines, the skipped names and the makespan.

The design

The class map, the main flow and the patterns that earn their place.

Scheduler class mapThe scheduler knows no policy by name. Order and the skip rule both come from the policy it is given.

The caller hands over the list of jobs.
The scheduler sorts them once with the policy's compare method.
For each job it finds the thread that becomes free first.
If the job may start there, the thread records its start and end.
If the policy says it cannot finish in time, the job goes to the skipped list.

Open on the whiteboardAll 2 diagrams on one tidy board, with a step-by-step walkthrough.

With every job ready at time 0, the order in which jobs are considered is fixed by the policy, so the whole plan is a greedy list schedule. schedule sorts the jobs once with policy.compare, then walks that order. For each job it finds the thread that frees up earliest, asks policy.canRun(job, start), and either places the job at that start time or records it as skipped.

The Strategy pattern is the whole point. The scheduler never mentions SJF, priority or deadlines. Ordering lives in compare and the skip rule lives in canRun, so the four required policies and a fifth one added in an interview are each one small class. Only EarliestDeadlinePolicy returns false from canRun; the other policies run every job even if its deadline is already missed. Each compare ends with the reported tie-breaks and then the input index, which keeps the printed order identical from run to run.

Why skipping at pick time is correct: the earliest free thread gives the smallest possible start time. If the job cannot meet its deadline from there, it cannot meet it on any other thread, and later jobs only start later, so the skip is final and never needs revisiting.

Steps for one job:

Take the next job in policy order.
Scan the thread slots for the smallest free time; ties go to the lowest thread id.
Ask the policy whether the job may start then. If not, add its name to skipped and continue.
Otherwise occupy the thread: record name, start and end, and move its free time to the end.

Cost is O(M log M) for the sort plus O(M times N) for the linear scan over threads. With a min-heap of thread free times the scan becomes O(log N). The result is a plain object, so printing and an executor are separate concerns.

Trade-off: this is an offline plan, which is simple and testable. If jobs arrive over time you need an event loop with a ready heap per policy and a clock that jumps to the next arrival or the next free thread, and canRun is then evaluated when the job is picked rather than when the plan is built.

The code

Runnable JavaScript, with the checks it passes.

flipkart-job-scheduler.js

const SUBMITTER_RANK = { ROOT: 0, ADMIN: 1, USER: 2 };

class Job {
  constructor(index, spec) {
    if (!spec.name) throw new Error("a job needs a name");
    if (!Number.isInteger(spec.duration) || spec.duration < 1) throw new Error("duration must be a positive integer");
    const priority = spec.priority ?? 0;
    if (!Number.isInteger(priority) || priority < 0) throw new Error("priority must be 0 or more");
    const submitter = spec.submitter ?? "USER";
    if (!(submitter in SUBMITTER_RANK)) throw new Error("unknown submitter " + submitter);
    this.index = index;
    this.name = spec.name;
    this.duration = spec.duration;
    this.priority = priority;
    this.deadline = spec.deadline ?? Infinity;
    this.submitter = submitter;
    this.rank = SUBMITTER_RANK[submitter];
  }
}

class FcfsPolicy {
  compare(a, b) {
    return a.index - b.index;
  }
  canRun() {
    return true;
  }
}

class ShortestJobFirstPolicy {
  compare(a, b) {
    return a.duration - b.duration || a.priority - b.priority || a.index - b.index;
  }
  canRun() {
    return true;
  }
}

class FixedPriorityPolicy {
  compare(a, b) {
    return a.priority - b.priority || a.rank - b.rank || b.duration - a.duration || a.index - b.index;
  }
  canRun() {
    return true;
  }
}

class EarliestDeadlinePolicy {
  compare(a, b) {
    return a.deadline - b.deadline || a.priority - b.priority || a.duration - b.duration || a.index - b.index;
  }
  canRun(job, start) {
    return start + job.duration <= job.deadline;
  }
}

class LongestJobFirstPolicy {
  compare(a, b) {
    return b.duration - a.duration || a.index - b.index;
  }
  canRun() {
    return true;
  }
}

class ThreadSlot {
  constructor(id) {
    this.id = id;
    this.freeAt = 0;
    this.runs = [];
  }
  occupy(job, start) {
    this.runs.push({ name: job.name, start, end: start + job.duration });
    this.freeAt = start + job.duration;
  }
}

class JobScheduler {
  constructor(threadCount, policy) {
    if (!Number.isInteger(threadCount) || threadCount < 1) throw new Error("need at least one thread");
    this.threadCount = threadCount;
    this.policy = policy;
  }
  earliestFree(slots) {
    let best = slots[0];
    for (const slot of slots) if (slot.freeAt < best.freeAt) best = slot;
    return best;
  }
  schedule(specs) {
    const slots = Array.from({ length: this.threadCount }, (_, id) => new ThreadSlot(id));
    const jobs = specs.map((spec, index) => new Job(index, spec));
    const ordered = [...jobs].sort((a, b) => this.policy.compare(a, b));
    const skipped = [];
    for (const job of ordered) {
      const slot = this.earliestFree(slots);
      if (!this.policy.canRun(job, slot.freeAt)) {
        skipped.push(job.name);
        continue;
      }
      slot.occupy(job, slot.freeAt);
    }
    const makespan = Math.max(...slots.map((slot) => slot.freeAt));
    return { threads: slots, skipped, makespan };
  }
  report(result) {
    return result.threads.map((slot) => "T" + slot.id + ": " + slot.runs.map((run) => run.name).join(", "));
  }
}

Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.

Try your own input

Write JavaScript that calls the code above and prints with console.log. It runs after the solution.

Extend it

The change requests an interviewer throws next.

Jobs now arrive over time instead of all being ready at time zero. What has to change in the algorithm, and where does the policy plug in?
Add pre-emption so a P0 job can interrupt a running P2 job. What state must a thread keep about the interrupted job?
A new policy must combine two rules, for example priority first and then earliest deadline. How do you build it without one class per combination?
Instead of skipping a late job under the deadline policy, run it last and report it as late. What changes?
With a million jobs and a thousand threads, how do you make finding the next free thread cheaper?

Where candidates slip

The mistakes this problem punishes.

Writing four if branches on a policy name inside the scheduler. The fifth policy then edits core code, which is the requirement change the round is designed to test.
Sorting without a tie-break. Equal durations, priorities or deadlines then print in an order that can differ between runs.
Applying the deadline skip to every policy, or to none. Only the deadline policy skips; check what the statement says for the others.
Checking the deadline against the start time instead of the finish time. A job that starts before its deadline but ends after it is late.
Always filling threads round robin instead of picking the earliest free one, which wastes capacity and gives wrong per-thread order.
Forgetting validation: zero threads, a zero or negative duration, an unknown submitter type, and an empty job list, which should give empty threads and a makespan of 0.

Have a go before you read.

Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.

Always show the answer straight away

Now make it stick

Sketch the class map on the whiteboard Run a mock interview

Where this was reported

Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.

Candidate write-upFlipkart Interview Experience, SDE-1 experienced (GeeksforGeeks)

Now make it stick

Where this was reported

More on schedulers and queues