LeetLLM
HardSchedulingPython 3

Dependency Scheduler With Retries

Run a dependency graph deterministically, retry transient failures, and reject invalid graphs.

45m3 sample tests6 hidden tests

Implement schedule(tasks, run, max_attempts=2).

Requirements

  • tasks is a list of dictionaries with id and optional deps (default empty).
  • Deduplicate each task's dependency list when building the graph so repeated edges leave indegree accurate.
  • A task can run when every unique dependency has completed.
  • Pick ready tasks in lexicographic order for deterministic output.
  • Call run(task_id) for each attempt.
  • If run raises, retry the same task immediately (before the next ready task) until max_attempts is exhausted.
  • Return task IDs in successful completion order.
  • Raise ValueError for cycles, missing dependencies, or duplicate task IDs.
  • Raise ValueError if max_attempts is not positive (max_attempts < 1).
  • Raise RuntimeError when a task fails all attempts.

Example

python
1tasks = [ 2 {"id": "extract", "deps": []}, 3 {"id": "embed", "deps": ["extract"]}, 4 {"id": "index", "deps": ["embed"]}, 5] 6 7assert schedule(tasks, lambda task_id: None) == ["extract", "embed", "index"]

Constraints

  • Single-threaded base version.
  • Use standard-library Python only.

Editor