Minimum Parallel Workers

A hard SQL interview practice problem on DataDriven. Write the query and run it against a real database, with instant feedback.

Domain

SQL

Difficulty

hard

Seniority

L5

Asked in

NVIDIA

Problem

We run batch jobs on a shared pool of workers, where a job occupies one worker from its start timestamp until its end timestamp. Find the smallest pool that could have run every completed job without any job ever waiting, counting a job that was logged across several rows only once.

Too few workers and it stalls.

Tables

batch_jobs

Columns: job_id INTEGER, job_name TEXT, status TEXT, rows_done INTEGER, started TEXT, ended TEXT, priority INTEGER, retries INTEGER

Expected output

Worked solution and explanation

What this problem really is

Beneath the capacity-planning story this is a sweep-line peak-overlap count. Every job is an interval from started to ended, and the smallest worker pool that never makes a job wait is exactly the largest number of intervals open at the same instant. Anyone can list the jobs; the move that separates candidates is turning each interval into two events, a +1 at started and a -1 at ended, and reading off the running total. Reach for COUNT(*) or MAX(retries) instead and you answer a completely different question.

Building it stage by stage

Step 1: Collapse duplicate job rows

A job that retried is logged on more than one row. SELECT DISTINCT job_id, started, ended folds those repeats back into a single interval before you count anything. Skip it and one job can inflate the peak on its own.

Step 2: Drop jobs that never finished

WHERE ended IS NOT NULL removes jobs that are still running or were canceled with no finish recorded. They have no measurable interval, and if you let one through, its start event has no matching -1 and the running total never comes back down. In this data started is always present, so the end filter is the one that actually changes the answer.

Step 3: Explode each interval into two events

UNION ALL a +1 row keyed on started with a -1 row keyed on ended. The whole schedule is now a single stream of arrivals and departures.

Step 4: Sweep with a running total

SUM(delta) OVER (ORDER BY event_time, delta DESC) walks the events in time order and keeps the live count. The delta DESC tie-break applies a start before an end at the same instant, so a job that begins exactly when another ends is counted as overlapping.

Step 5: Take the busiest instant

MAX(concurrent) over those running totals is the peak overlap, which is the minimum number of workers you must provision.

The solution

WITH jobs AS (
    SELECT DISTINCT job_id, started, ended
    FROM batch_jobs
    WHERE ended IS NOT NULL
),
events AS (
    SELECT started AS event_time, 1 AS delta FROM jobs
    UNION ALL
    SELECT ended AS event_time, -1 AS delta FROM jobs
),
running AS (
    SELECT event_time,
        SUM(delta) OVER (ORDER BY event_time, delta DESC) AS concurrent
    FROM events
)
SELECT MAX(concurrent) AS min_workers
FROM running

Common follow-up questions

• How would you also report the time window during which the peak occurred, not just its size? (Tests carrying `event_time` through the sweep instead of collapsing straight to the maximum.)
• With a million rows and no index on `started` or `ended`, what would you add to keep the sort cheap? (Tests indexing knowledge for the sort that drives the sweep.)
• How would you extend this to report peak concurrency per day rather than one number overall? (Tests partitioning the sweep into buckets.)