Job Placement Scheduler (Go)
Topics: backtracking, constraint satisfaction, scheduling
Problem
Place a batch of jobs onto a set of nodes — like a Kubernetes scheduler deciding which node gets
which pod — subject to per-node capacity, affinity (must be co-located), and anti-affinity
(must not be co-located).
type Job struct {
Name string
CPU int
}
type Node struct {
Name string
CPU int
}
func Place(jobs []Job, nodes []Node, affinity, antiAffinity [][2]string) (map[string]string, bool)
Place returns a map from job name to node name and true if a valid assignment exists, or
nil, false if every combination is infeasible:
- For each node, the sum of
CPU of the jobs placed on it must not exceed the node's CPU.
- Every pair of job names in
affinity must end up on the same node.
- No pair of job names in
antiAffinity may end up on the same node.
jobs: j1(6) j2(6) nodes: a(8) b(8) -> split across a and b (12 > 8)
jobs: j1(2) j2(2) nodes: a(10) b(10) anti: j1,j2 -> different nodes (capacity allows together,
anti-affinity forbids it)
jobs: j1(6) j2(6) nodes: a(10) b(10) aff: j1,j2 -> infeasible (12 > either node's capacity)
Key concepts
- This is N-Queens with a cluster as the board. Place
jobs[0] on the first node where it fits
and is compatible with anything already placed, recurse on the rest, and if every node for
jobs[0] leads to a dead end further down, undo and report failure up to the caller — which
then tries a different node for its job.
- Why backtracking, not greedy: a first-fit placement can use up exactly the node an
affinity-linked job later needs, with no node left that satisfies both. Only undoing the earlier
choice and retrying it on another node finds the valid assignment (see the
AffinityRequiresBacktracking test).
compatible(job, node, ...) only needs to check partners that are already placed: if an
affinity partner is on a different node, or an anti-affinity partner is on the same node, this
node is out for job. A partner not yet placed imposes no constraint yet — its own placement
will check back against job.
- Proving infeasibility: when no assignment exists (total demand over capacity, an
affinity-linked pair too big for any single node, or more mutually anti-affine jobs than nodes),
the search must exhaust every combination before returning
false.
The struct, Job, and Node are provided; you implement Place.
Run
go test -v ./challenges/job-placement/go/
Sign in to submit your solution.