TL;DR: Order waiting jobs by priority and submission sequence. Start the head when it fits; otherwise consider only lower-priority running jobs for preemption. Choose victims according to a stated policy, and keep their original queue sequence when they return. A greedy victim list is not necessarily a minimum-cost or minimum-count set, and strict priority alone does not guarantee progress for every job.
How to approach it
Define the priority convention, resource model and preemption semantics before coding. Implement admission, completion and input validation, then trace an equal-priority arrival and a higher-priority arrival. Explain the fairness and physical-release behavior that a production scheduler would need beyond this in-memory model.
A strong answer
An eight-GPU pool runs two four-GPU jobs. A higher-priority four-GPU job arrives. Reclaiming one lower-priority job is sufficient; evicting both would add disruption without helping this placement. The scheduler needs to calculate the deficit and stop selecting victims when its policy has enough capacity.
GPU Job Scheduler Design explains admission and placement. This exercise uses one interchangeable resource count and models preemption as immediate. It does not send termination commands or manage real GPU ownership.
State the policy before choosing the data structure
Lower priority numbers mean more important jobs. Equal priorities use submission order. A waiting job can preempt only a strictly lower-priority running job. Among eligible victims, choose the lowest importance first and then the latest original submission. That tie-break is deterministic; it is not a measurement of runtime or lost progress.
import heapq
import itertools
class Scheduler:
"""Single-threaded count model; preemption releases capacity instantly."""
def __init__(self, capacity):
if type(capacity) is not int or capacity <= 0:
raise ValueError("capacity must be a positive integer")
self.capacity = capacity
self.waiting = [] # (priority, submission sequence, ID, size)
self.running = {} # ID -> the same tuple
self.active = set()
self.sequence = itertools.count()
def submit(self, job_id, priority, size):
if not isinstance(job_id, str) or not job_id or job_id in self.active:
raise ValueError("job ID must be nonempty and unique among active jobs")
if type(priority) is not int:
raise ValueError("priority must be an integer")
if type(size) is not int or not 1 <= size <= self.capacity:
raise ValueError("job size cannot fit this pool")
job = (priority, next(self.sequence), job_id, size)
self.active.add(job_id)
heapq.heappush(self.waiting, job)
return self._schedule()
def finish(self, job_id):
del self.running[job_id] # KeyError if the job is not running
self.active.remove(job_id)
return [("finish", job_id)] + self._schedule()
def _schedule(self):
events = []
while self.waiting:
head = self.waiting[0]
free = self.capacity - sum(j[3] for j in self.running.values())
if head[3] <= free:
heapq.heappop(self.waiting)
self.running[head[2]] = head
events.append(("start", head[2]))
continue
candidates = [j for j in self.running.values() if j[0] > head[0]]
candidates.sort(key=lambda j: (-j[0], -j[1]))
chosen, available = [], free
for job in candidates:
chosen.append(job)
available += job[3]
if available >= head[3]:
break
if available < head[3]:
break # no mutation when this head cannot be admitted
for job in chosen:
del self.running[job[2]]
heapq.heappush(self.waiting, job) # original sequence survives
events.append(("preempt", job[2]))
return events
The heap uses Python's standard priority-queue ordering pattern. Validation rejects oversized jobs before they can permanently block this pool's queue. Completion frees capacity and reruns admission; without that path, waiting jobs would have no ordinary way to resume.
Trace ownership and order
s = Scheduler(8)
assert s.submit("low1", 5, 4) == [("start", "low1")]
assert s.submit("low2", 5, 4) == [("start", "low2")]
assert s.submit("high", 1, 4) == [("preempt", "low2"), ("start", "high")]
assert s.submit("low3", 5, 4) == []
assert s.finish("high") == [("finish", "high"), ("start", "low2")]
assert {j[2] for j in s.waiting} == {"low3"}
assert sum(j[3] for j in s.running.values()) == 8
low2 returns ahead of low3 because its original submission sequence remains smaller. This preserves their local tie order; it does not guarantee that either will run under an endless stream of higher-priority work.
The toy eight-GPU pool models release as immediate.
- low1 and low2 each use four GPUs
Both have priority 5; low2 was submitted later.
- A priority-1 job needs four GPUs
The declared policy preempts low2 and starts high.
- high finishes; low2 resumes before low3
The original sequence survives preemption, but higher-priority arrivals can still delay it.
The selected victims are sufficient under this greedy order, not mathematically minimal:
Free = 0; incoming job needs 8 GPUs
Eligible victims in policy order = 3, 3, 8 GPUs
Greedy selection = 3 + 3 + 8 = 14 GPUs across three victims
Minimum-count alternative = the single 8-GPU victim
sanity: stopping as soon as the ordered prefix fits does not optimize over all subsets.
That may be an intentional preference for evicting lower-importance work before higher-importance work. If lost progress matters, define a cost model and compare candidate sets accordingly. Submission recency alone says little about checkpoint age, useful progress or restart cost.
Make the model's limits explicit
The loop stops when its head cannot fit. That can leave devices idle even when a smaller queued job could run. Backfill is an alternative, but protecting the head's expected start may require reservations and runtime assumptions. Multi-Tenancy, Quotas and Fair Share explains broader policy choices.
Aging can increase a waiting job's priority. For example, 5 - waited_hours reaches priority 1 after four hours. That equality does not promise a four-hour wait bound: capacity, running-job duration, tie-breaking and arrivals still matter. If effective priorities change over time, the queue must be updated or evaluated accordingly; this code implements no aging.
A real preemption also has a release sequence: request checkpoint or stop, confirm the old workers cannot use the devices, then admit the replacement. Requeueing a record is not confirmation of physical release. Use attempt identity and ownership controls so delayed messages from old workers cannot affect a new attempt. Waiting for a near-complete job can be better than reclaiming it, depending on urgency and lost work.
For complexity, candidate sorting costs up to O(R log R) for R running jobs per selection. Several admissions and requeues can occur in one call. The heap does not make the whole scheduling operation O(log N).
What interviewers probe next
- “Does this choose the fewest victims?” No; it chooses a sufficient prefix under the declared priority policy.
- “Can low-priority jobs starve?” Yes; progress guarantees require additional policy and feasibility assumptions.
- “When may a real replacement start?” After the required placement and verified release of prior ownership.
Common mistakes
- Calling submission sequence the time a job last started.
- Treating a greedy prefix as an optimal victim set.
- Claiming aging alone gives a fixed maximum wait.
- Reusing devices when only the scheduler record says a victim stopped.
Key takeaways
- In the eight-GPU trace, one four-GPU victim is sufficient and keeps its original queue position.
- The 3, 3, 8 example shows why a sufficient victim prefix need not be minimal.
- Keep ordering, fairness and physical resource ownership as explicit parts of the design.