go-06-job-scheduler
1.000
Challenge · difficulty 5/5
# Dependency-aware job scheduler
Implement a file **`solution.go`** in `package challenge` exporting:
```go
type Job struct {
ID string
Deps []string
Priority int
}
func Schedule(jobs []Job) ([]string, error)
```
`Schedule` computes a valid execution order for `jobs` and returns the slice of
job IDs in that order. The order is a **topological order**: a job may appear in
the output only after every ID in its `Deps` has already appeared earlier.
## Selection rule (deterministic)
Many topological orders may exist; this challenge fixes a single one. Build the
output by repeating the following step until every job is scheduled:
1. Consider the set of **ready** jobs: not-yet-scheduled jobs whose dependencies
are *all* already scheduled.
2. Among the ready jobs, pick the one with the **highest `Priority`**.
3. Break ties (equal `Priority`) by the **lexicographically smallest `ID`**
(Go string `<`).
4. Append the chosen job's ID to the output, mark it scheduled, and repeat.
This makes the result unique and fully determined by the input.
## Rules
- The output is a slice of job IDs (`[]string`). Every job appears exactly once.
- An **empty input** (`nil` or `len 0`) returns an empty (`len 0`) slice and a
`nil` error.
- Return a non-nil error and a `nil`/empty slice when any of these hold:
- **Duplicate ID** — two jobs share the same `ID`.
- **Unknown dependency** — some job's `Deps` references an ID that is not the
`ID` of any job in `jobs`.
- **Cycle** — the dependencies form a cycle, so some jobs can never become
ready. A self-dependency (`a` depends on `a`) is a cycle.
- Duplicate entries inside a single job's `Deps` are allowed and harmless: the
dependency just needs to be satisfied once.
## Examples
Linear chain — `c` depends on `b`, `b` depends on `a`:
```go
Schedule([]Job{
{ID: "c", Deps: []string{"b"}},
{ID: "b", Deps: []string{"a"}},
{ID: "a"},
})
// → ["a", "b", "c"], nil
```
Priority tie-break — `a` and `b` are both ready immediately; `b` has the higher
priority, so it runs first:
```go
Schedule([]Job{
{ID: "a", Priority: 1},
{ID: "b", Priority: 5},
})
// → ["b", "a"], nil
```
ID tie-break — equal priorities, so the smaller ID wins:
```go
Schedule([]Job{
{ID: "y", Priority: 0},
{ID: "x", Priority: 0},
})
// → ["x", "y"], nil
```
Diamond — `d` depends on both `b` and `c`, which both depend on `a`. With equal
priorities the smaller ID breaks the `b`/`c` tie:
```go
Schedule([]Job{
{ID: "a"},
{ID: "b", Deps: []string{"a"}},
{ID: "c", Deps: []string{"a"}},
{ID: "d", Deps: []string{"b", "c"}},
})
// → ["a", "b", "c", "d"], nil
```
Cycle — returns an error:
```go
Schedule([]Job{
{ID: "a", Deps: []string{"b"}},
{ID: "b", Deps: []string{"a"}},
})
// → nil, <error>
```
Use only the Go standard library.
tests/solution_test.go
package challenge
import (
"reflect"
"testing"
)
func TestScheduleEmpty(t *testing.T) {
got, err := Schedule(nil)
if err != nil {
t.Fatalf("Schedule(nil) error = %v, want nil", err)
}
if len(got) != 0 {
t.Fatalf("Schedule(nil) = %v, want empty slice", got)
}
got, err = Schedule([]Job{})
if err != nil {
t.Fatalf("Schedule([]) error = %v, want nil", err)
}
if len(got) != 0 {
t.Fatalf("Schedule([]) = %v, want empty slice", got)
}
}
func TestScheduleSingle(t *testing.T) {
got, err := Schedule([]Job{{ID: "only"}})
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
if want := []string{"only"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestScheduleLinearChain(t *testing.T) {
jobs := []Job{
{ID: "c", Deps: []string{"b"}},
{ID: "b", Deps: []string{"a"}},
{ID: "a"},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
if want := []string{"a", "b", "c"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestScheduleDiamond(t *testing.T) {
jobs := []Job{
{ID: "d", Deps: []string{"b", "c"}},
{ID: "b", Deps: []string{"a"}},
{ID: "c", Deps: []string{"a"}},
{ID: "a"},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
// Equal priorities: a first, then b<c by ID, then d.
if want := []string{"a", "b", "c", "d"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestSchedulePriorityTieBreak(t *testing.T) {
jobs := []Job{
{ID: "a", Priority: 1},
{ID: "b", Priority: 5},
{ID: "c", Priority: 3},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
// All ready; ordered by descending priority: b(5), c(3), a(1).
if want := []string{"b", "c", "a"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestScheduleSmallestIDTieBreak(t *testing.T) {
jobs := []Job{
{ID: "y", Priority: 0},
{ID: "x", Priority: 0},
{ID: "z", Priority: 0},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
// Equal priorities: lexicographic by ID.
if want := []string{"x", "y", "z"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestSchedulePriorityBeatsID(t *testing.T) {
// "z" has higher priority than "a", so it must come first even though
// "a" is the smaller ID.
jobs := []Job{
{ID: "a", Priority: 1},
{ID: "z", Priority: 9},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
if want := []string{"z", "a"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestScheduleIndependentJobs(t *testing.T) {
jobs := []Job{
{ID: "b"},
{ID: "a"},
{ID: "d"},
{ID: "c"},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
// No deps, all priority 0: pure lexicographic order.
if want := []string{"a", "b", "c", "d"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestSchedulePriorityRespectsDependencies(t *testing.T) {
// "low" has lower priority but is the only dependency-free job, so it
// must run before the high-priority job that depends on it.
jobs := []Job{
{ID: "high", Deps: []string{"low"}, Priority: 100},
{ID: "low", Priority: 1},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
if want := []string{"low", "high"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestScheduleComplexDeterministic(t *testing.T) {
jobs := []Job{
{ID: "build", Deps: []string{"compile"}, Priority: 5},
{ID: "compile", Deps: []string{"fetch"}, Priority: 5},
{ID: "fetch", Priority: 5},
{ID: "lint", Deps: []string{"fetch"}, Priority: 10},
{ID: "test", Deps: []string{"build", "lint"}, Priority: 1},
{ID: "docs", Deps: []string{"fetch"}, Priority: 10},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
// fetch first (only ready). Then ready={compile(5), lint(10), docs(10)}.
// docs and lint tie at 10 -> docs < lint by ID. Then lint. Then compile.
// After compile -> build ready. build(5). Then test.
want := []string{"fetch", "docs", "lint", "compile", "build", "test"}
if !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestScheduleDuplicateDepsIgnored(t *testing.T) {
jobs := []Job{
{ID: "b", Deps: []string{"a", "a", "a"}},
{ID: "a"},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
if want := []string{"a", "b"}; !reflect.DeepEqual(got, want) {
t.Fatalf("Schedule = %v, want %v", got, want)
}
}
func TestScheduleCycleError(t *testing.T) {
jobs := []Job{
{ID: "a", Deps: []string{"b"}},
{ID: "b", Deps: []string{"a"}},
}
got, err := Schedule(jobs)
if err == nil {
t.Fatalf("expected error for cycle, got order %v", got)
}
if len(got) != 0 {
t.Fatalf("on cycle error, want empty slice, got %v", got)
}
}
func TestScheduleLongerCycleError(t *testing.T) {
jobs := []Job{
{ID: "x"}, // schedulable
{ID: "a", Deps: []string{"c"}},
{ID: "b", Deps: []string{"a"}},
{ID: "c", Deps: []string{"b"}},
}
got, err := Schedule(jobs)
if err == nil {
t.Fatalf("expected error for 3-node cycle, got order %v", got)
}
if len(got) != 0 {
t.Fatalf("on cycle error, want empty slice, got %v", got)
}
}
func TestScheduleSelfDependencyError(t *testing.T) {
jobs := []Job{
{ID: "a", Deps: []string{"a"}},
}
got, err := Schedule(jobs)
if err == nil {
t.Fatalf("expected error for self-dependency, got order %v", got)
}
if len(got) != 0 {
t.Fatalf("on self-dependency error, want empty slice, got %v", got)
}
}
func TestScheduleUnknownDepError(t *testing.T) {
jobs := []Job{
{ID: "a", Deps: []string{"ghost"}},
}
got, err := Schedule(jobs)
if err == nil {
t.Fatalf("expected error for unknown dep, got order %v", got)
}
if len(got) != 0 {
t.Fatalf("on unknown-dep error, want empty slice, got %v", got)
}
}
func TestScheduleDuplicateIDError(t *testing.T) {
jobs := []Job{
{ID: "a"},
{ID: "a"},
}
got, err := Schedule(jobs)
if err == nil {
t.Fatalf("expected error for duplicate ID, got order %v", got)
}
if len(got) != 0 {
t.Fatalf("on duplicate-ID error, want empty slice, got %v", got)
}
}
func TestScheduleOutputIsValidTopoOrder(t *testing.T) {
jobs := []Job{
{ID: "a"},
{ID: "b", Deps: []string{"a"}},
{ID: "c", Deps: []string{"a"}},
{ID: "d", Deps: []string{"b", "c"}},
{ID: "e", Deps: []string{"d"}},
}
got, err := Schedule(jobs)
if err != nil {
t.Fatalf("unexpected error: %v", err)
}
if len(got) != len(jobs) {
t.Fatalf("got %d ids, want %d", len(got), len(jobs))
}
pos := make(map[string]int, len(got))
for i, id := range got {
if _, dup := pos[id]; dup {
t.Fatalf("id %q appears more than once in %v", id, got)
}
pos[id] = i
}
for _, j := range jobs {
for _, dep := range j.Deps {
if pos[dep] >= pos[j.ID] {
t.Fatalf("dependency %q (pos %d) not before %q (pos %d) in %v",
dep, pos[dep], j.ID, pos[j.ID], got)
}
}
}
}
System prompt
You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.
Proposed solution
```go
package challenge
import (
"errors"
"sort"
)
type Job struct {
ID string
Deps []string
Priority int
}
func Schedule(jobs []Job) ([]string, error) {
// Handle empty input
if len(jobs) == 0 {
return []string{}, nil
}
// Build a map of job IDs for quick lookup and check for duplicates
idMap := make(map[string]Job)
for _, job := range jobs {
if _, exists := idMap[job.ID]; exists {
return nil, errors.New("duplicate ID")
}
idMap[job.ID] = job
}
// Check for unknown dependencies
for _, job := range jobs {
for _, dep := range job.Deps {
if _, exists := idMap[dep]; !exists {
return nil, errors.New("unknown dependency")
}
}
}
// Build adjacency list and in-degree count
// We'll use Kahn's algorithm with a priority queue
inDegree := make(map[string]int)
dependents := make(map[string][]string) // jobID -> list of jobs that depend on it
for _, job := range jobs {
inDegree[job.ID] = len(job.Deps)
for _, dep := range job.Deps {
dependents[dep] = append(dependents[dep], job.ID)
}
}
// Initialize ready queue with jobs that have no dependencies
type readyJob struct {
id string
priority int
}
ready := make([]readyJob, 0)
for id, deg := range inDegree {
if deg == 0 {
ready = append(ready, readyJob{id: id, priority: idMap[id].Priority})
}
}
// Sort ready jobs by priority (descending) and then by ID (ascending)
sort.Slice(ready, func(i, j int) bool {
if ready[i].priority != ready[j].priority {
return ready[i].priority > ready[j].priority // Higher priority first
}
return ready[i].id < ready[j].id // Lexicographically smaller ID first
})
result := make([]string, 0, len(jobs))
scheduled := make(map[string]bool)
for len(ready) > 0 {
// Take the highest priority job (with tie-breaking)
current := ready[0]
ready = ready[1:]
result = append(result, current.id)
scheduled[current.id] = true
// Update in-degrees and find new ready jobs
for _, dependentID := range dependents[current.id] {
inDegree[dependentID]--
if inDegree[dependentID] == 0 && !scheduled[dependentID] {
ready = append(ready, readyJob{id: dependentID, priority: idMap[dependentID].Priority})
}
}
// Re-sort ready queue after adding new jobs
sort.Slice(ready, func(i, j int) bool {
if ready[i].priority != ready[j].priority {
return ready[i].priority > ready[j].priority
}
return ready[i].id < ready[j].id
})
}
// Check if all jobs were scheduled (no cycles)
if len(result) != len(jobs) {
return nil, errors.New("cycle detected")
}
return result, nil
}
```Test output (stdout)
run","Package":"challenge","Test":"TestScheduleCycleError"}
{"Time":"2026-07-01T22:49:18.474592024+02:00","Action":"output","Package":"challenge","Test":"TestScheduleCycleError","Output":"=== RUN TestScheduleCycleError\n"}
{"Time":"2026-07-01T22:49:18.474593194+02:00","Action":"output","Package":"challenge","Test":"TestScheduleCycleError","Output":"--- PASS: TestScheduleCycleError (0.00s)\n"}
{"Time":"2026-07-01T22:49:18.474594984+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleCycleError","Elapsed":0}
{"Time":"2026-07-01T22:49:18.474595974+02:00","Action":"run","Package":"challenge","Test":"TestScheduleLongerCycleError"}
{"Time":"2026-07-01T22:49:18.474597174+02:00","Action":"output","Package":"challenge","Test":"TestScheduleLongerCycleError","Output":"=== RUN TestScheduleLongerCycleError\n"}
{"Time":"2026-07-01T22:49:18.474598314+02:00","Action":"output","Package":"challenge","Test":"TestScheduleLongerCycleError","Output":"--- PASS: TestScheduleLongerCycleError (0.00s)\n"}
{"Time":"2026-07-01T22:49:18.474600444+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleLongerCycleError","Elapsed":0}
{"Time":"2026-07-01T22:49:18.474601404+02:00","Action":"run","Package":"challenge","Test":"TestScheduleSelfDependencyError"}
{"Time":"2026-07-01T22:49:18.474602264+02:00","Action":"output","Package":"challenge","Test":"TestScheduleSelfDependencyError","Output":"=== RUN TestScheduleSelfDependencyError\n"}
{"Time":"2026-07-01T22:49:18.474603324+02:00","Action":"output","Package":"challenge","Test":"TestScheduleSelfDependencyError","Output":"--- PASS: TestScheduleSelfDependencyError (0.00s)\n"}
{"Time":"2026-07-01T22:49:18.474604384+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleSelfDependencyError","Elapsed":0}
{"Time":"2026-07-01T22:49:18.474605344+02:00","Action":"run","Package":"challenge","Test":"TestScheduleUnknownDepError"}
{"Time":"2026-07-01T22:49:18.474606194+02:00","Action":"output","Package":"challenge","Test":"TestScheduleUnknownDepError","Output":"=== RUN TestScheduleUnknownDepError\n"}
{"Time":"2026-07-01T22:49:18.474607344+02:00","Action":"output","Package":"challenge","Test":"TestScheduleUnknownDepError","Output":"--- PASS: TestScheduleUnknownDepError (0.00s)\n"}
{"Time":"2026-07-01T22:49:18.474608324+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleUnknownDepError","Elapsed":0}
{"Time":"2026-07-01T22:49:18.474609304+02:00","Action":"run","Package":"challenge","Test":"TestScheduleDuplicateIDError"}
{"Time":"2026-07-01T22:49:18.474610114+02:00","Action":"output","Package":"challenge","Test":"TestScheduleDuplicateIDError","Output":"=== RUN TestScheduleDuplicateIDError\n"}
{"Time":"2026-07-01T22:49:18.474611354+02:00","Action":"output","Package":"challenge","Test":"TestScheduleDuplicateIDError","Output":"--- PASS: TestScheduleDuplicateIDError (0.00s)\n"}
{"Time":"2026-07-01T22:49:18.474612964+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleDuplicateIDError","Elapsed":0}
{"Time":"2026-07-01T22:49:18.474613854+02:00","Action":"run","Package":"challenge","Test":"TestScheduleOutputIsValidTopoOrder"}
{"Time":"2026-07-01T22:49:18.474614724+02:00","Action":"output","Package":"challenge","Test":"TestScheduleOutputIsValidTopoOrder","Output":"=== RUN TestScheduleOutputIsValidTopoOrder\n"}
{"Time":"2026-07-01T22:49:18.474616945+02:00","Action":"output","Package":"challenge","Test":"TestScheduleOutputIsValidTopoOrder","Output":"--- PASS: TestScheduleOutputIsValidTopoOrder (0.00s)\n"}
{"Time":"2026-07-01T22:49:18.474618245+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleOutputIsValidTopoOrder","Elapsed":0}
{"Time":"2026-07-01T22:49:18.474619175+02:00","Action":"output","Package":"challenge","Output":"PASS\n"}
{"Time":"2026-07-01T22:49:18.474812465+02:00","Action":"output","Package":"challenge","Output":"ok \tchallenge\t0.001s\n"}
{"Time":"2026-07-01T22:49:18.474824066+02:00","Action":"pass","Package":"challenge","Elapsed":0.001}