Problem

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/

Leaderboard score: lower is better, 1.0 ≈ reference

#	Name	score	ns/op	allocs

Output

No submission yet.