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"
"fmt"
"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 ID to Job for quick lookup
jobMap := make(map[string]Job)
ids := make(map[string]bool)
// Check for duplicate IDs and build job map
for _, job := range jobs {
if ids[job.ID] {
return nil, fmt.Errorf("duplicate job ID: %s", job.ID)
}
ids[job.ID] = true
jobMap[job.ID] = job
}
// Check for unknown dependencies
for _, job := range jobs {
for _, dep := range job.Deps {
if !ids[dep] {
return nil, fmt.Errorf("unknown dependency: %s", dep)
}
}
}
// Check for cycles using DFS with three states:
// 0 = unvisited, 1 = visiting (in current path), 2 = visited (completed)
state := make(map[string]int)
for id := range ids {
state[id] = 0
}
var hasCycle bool
var dfs func(id string) bool
dfs = func(id string) bool {
if state[id] == 1 {
return true // Cycle detected
}
if state[id] == 2 {
return false // Already processed
}
state[id] = 1 // Mark as visiting
job := jobMap[id]
for _, dep := range job.Deps {
if dfs(dep) {
return true
}
}
state[id] = 2 // Mark as visited
return false
}
for id := range ids {
if state[id] == 0 {
if dfs(id) {
hasCycle = true
break
}
}
}
if hasCycle {
return nil, errors.New("cycle detected in dependencies")
}
// Schedule jobs using the selection rule
scheduled := make(map[string]bool)
result := []string{}
for len(result) < len(jobs) {
// Find ready jobs (not scheduled, all deps satisfied)
ready := []Job{}
for _, job := range jobs {
if !scheduled[job.ID] {
allDepsSatisfied := true
for _, dep := range job.Deps {
if !scheduled[dep] {
allDepsSatisfied = false
break
}
}
if allDepsSatisfied {
ready = append(ready, job)
}
}
}
if len(ready) == 0 {
return nil, errors.New("cycle detected in dependencies")
}
// Sort ready jobs by priority (descending) 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
}
return ready[i].ID < ready[j].ID
})
// Pick the first job
chosen := ready[0]
result = append(result, chosen.ID)
scheduled[chosen.ID] = true
}
return result, nil
}
```Test output (stdout)
n":"run","Package":"challenge","Test":"TestScheduleCycleError"}
{"Time":"2026-07-02T04:35:42.29715831+02:00","Action":"output","Package":"challenge","Test":"TestScheduleCycleError","Output":"=== RUN TestScheduleCycleError\n"}
{"Time":"2026-07-02T04:35:42.29716055+02:00","Action":"output","Package":"challenge","Test":"TestScheduleCycleError","Output":"--- PASS: TestScheduleCycleError (0.00s)\n"}
{"Time":"2026-07-02T04:35:42.29716147+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleCycleError","Elapsed":0}
{"Time":"2026-07-02T04:35:42.29716234+02:00","Action":"run","Package":"challenge","Test":"TestScheduleLongerCycleError"}
{"Time":"2026-07-02T04:35:42.297163119+02:00","Action":"output","Package":"challenge","Test":"TestScheduleLongerCycleError","Output":"=== RUN TestScheduleLongerCycleError\n"}
{"Time":"2026-07-02T04:35:42.297164619+02:00","Action":"output","Package":"challenge","Test":"TestScheduleLongerCycleError","Output":"--- PASS: TestScheduleLongerCycleError (0.00s)\n"}
{"Time":"2026-07-02T04:35:42.297166309+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleLongerCycleError","Elapsed":0}
{"Time":"2026-07-02T04:35:42.297167149+02:00","Action":"run","Package":"challenge","Test":"TestScheduleSelfDependencyError"}
{"Time":"2026-07-02T04:35:42.297167959+02:00","Action":"output","Package":"challenge","Test":"TestScheduleSelfDependencyError","Output":"=== RUN TestScheduleSelfDependencyError\n"}
{"Time":"2026-07-02T04:35:42.297170839+02:00","Action":"output","Package":"challenge","Test":"TestScheduleSelfDependencyError","Output":"--- PASS: TestScheduleSelfDependencyError (0.00s)\n"}
{"Time":"2026-07-02T04:35:42.297171979+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleSelfDependencyError","Elapsed":0}
{"Time":"2026-07-02T04:35:42.297173059+02:00","Action":"run","Package":"challenge","Test":"TestScheduleUnknownDepError"}
{"Time":"2026-07-02T04:35:42.297173839+02:00","Action":"output","Package":"challenge","Test":"TestScheduleUnknownDepError","Output":"=== RUN TestScheduleUnknownDepError\n"}
{"Time":"2026-07-02T04:35:42.297176959+02:00","Action":"output","Package":"challenge","Test":"TestScheduleUnknownDepError","Output":"--- PASS: TestScheduleUnknownDepError (0.00s)\n"}
{"Time":"2026-07-02T04:35:42.297178129+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleUnknownDepError","Elapsed":0}
{"Time":"2026-07-02T04:35:42.297179259+02:00","Action":"run","Package":"challenge","Test":"TestScheduleDuplicateIDError"}
{"Time":"2026-07-02T04:35:42.297180059+02:00","Action":"output","Package":"challenge","Test":"TestScheduleDuplicateIDError","Output":"=== RUN TestScheduleDuplicateIDError\n"}
{"Time":"2026-07-02T04:35:42.297181419+02:00","Action":"output","Package":"challenge","Test":"TestScheduleDuplicateIDError","Output":"--- PASS: TestScheduleDuplicateIDError (0.00s)\n"}
{"Time":"2026-07-02T04:35:42.297182679+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleDuplicateIDError","Elapsed":0}
{"Time":"2026-07-02T04:35:42.297184419+02:00","Action":"run","Package":"challenge","Test":"TestScheduleOutputIsValidTopoOrder"}
{"Time":"2026-07-02T04:35:42.297185409+02:00","Action":"output","Package":"challenge","Test":"TestScheduleOutputIsValidTopoOrder","Output":"=== RUN TestScheduleOutputIsValidTopoOrder\n"}
{"Time":"2026-07-02T04:35:42.297202149+02:00","Action":"output","Package":"challenge","Test":"TestScheduleOutputIsValidTopoOrder","Output":"--- PASS: TestScheduleOutputIsValidTopoOrder (0.00s)\n"}
{"Time":"2026-07-02T04:35:42.297203469+02:00","Action":"pass","Package":"challenge","Test":"TestScheduleOutputIsValidTopoOrder","Elapsed":0}
{"Time":"2026-07-02T04:35:42.297204599+02:00","Action":"output","Package":"challenge","Output":"PASS\n"}
{"Time":"2026-07-02T04:35:42.297320829+02:00","Action":"output","Package":"challenge","Output":"ok \tchallenge\t0.001s\n"}
{"Time":"2026-07-02T04:35:42.297340129+02:00","Action":"pass","Package":"challenge","Elapsed":0.001}
Reasoning (chain-of-thought)
The user wants me to implement a dependency-aware job scheduler in Go. Let me break down the requirements:
1. **Job struct**: Has ID, Deps (dependencies), and Priority
2. **Schedule function**: Takes a slice of Job, returns ([]string, error)
3. **Topological order**: Jobs must appear after their dependencies
4. **Selection rule**:
- Pick ready jobs (all deps satisfied)
- Highest Priority first
- Lexicographically smallest ID for ties
5. **Error conditions**:
- Duplicate IDs
- Unknown dependencies
- Cycles
Let me think through the implementation:
1. First, validate the input:
- Check for duplicate IDs
- Check for unknown dependencies
- Check for cycles
2. Then, implement the scheduling algorithm:
- Maintain a set of scheduled jobs
- In each iteration, find all ready jobs (not scheduled, all deps satisfied)
- Sort ready jobs by priority (descending) then by ID (ascending)
- Pick the first one, add to output, mark as scheduled
- Repeat until all jobs are scheduled
Let me write the code:
```go
package challenge
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 ID to Job for quick lookup
jobMap := make(map[string]Job)
ids := make(map[string]bool)
// Check for duplicate IDs and build job map
for _, job := range jobs {
if ids[job.ID] {
return nil, fmt.Errorf("duplicate job ID: %s", job.ID)
}
ids[job.ID] = true
jobMap[job.ID] = job
}
// Check for unknown dependencies
for _, job := range jobs {
for _, dep := range job.Deps {
if !ids[dep] {
return nil, fmt.Errorf("unknown dependency: %s", dep)
}
}
}
// Check for cycles using DFS
// States: 0 = unvisited, 1 = visiting, 2 = visited
state := make(map[string]int)
for id := range ids {
state[id] = 0
}
var hasCycle bool
var dfs func(id string) bool
dfs = func(id string) bool {
if state[id] == 1 {
return true // Cycle detected
}
if state[id] == 2 {
return false // Already processed
}
state[id] = 1 // Mark as visiting
job := jobMap[id]
for _, dep := range job.Deps {
if dfs(dep) {
return true
}
}
state[id] = 2 // Mark as visited
return false
}
for id := range ids {
if state[id] == 0 {
if dfs(id) {
hasCycle = true
break
}
}
}
if hasCycle {
return nil, fmt.Errorf("cycle detected in dependencies")
}
// Schedule jobs
scheduled := make(map[string]bool)
result := []string{}
for len(result) < len(jobs) {
// Find ready jobs
ready := []Job{}
for _, job := range jobs {
if !scheduled[job.ID] {
// Check if all dependencies are satisfied
allDepsSatisfied := true
for _, dep := range job.Deps {
if !scheduled[dep] {
allDepsSatisfied = false
break
}
}
if allDepsSatisfied {
ready = append(ready, job)
}
}
}
if len(ready) == 0 {
return nil, fmt.Errorf("cycle detected in dependencies")
}
// Sort ready jobs by priority (descending) 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
}
return ready[i].ID < ready[j].ID
})
// Pick the first job
chosen := ready[0]
result = append(result, chosen.ID)
scheduled[chosen.ID] = true
}
return result, nil
}
```
I'm realizing the cycle detection needs more careful consideration. The current implementation might not catch all cycle scenarios correctly. I'll need to refine the approach to ensure comprehensive cycle detection.
The key challenge is handling complex dependency graphs where cycles might not be immediately obvious. A more robust cycle detection algorithm will be crucial for ensuring the scheduling logic works correctly across different job configurations.
I'll focus on creating a more precise method to identify and handle potential circular dependencies before attempting to schedule jobs.