Katkat
Back

Event-Kitchen Prep Scheduler: Dependencies, Priority, Filters

RipplingSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Build a scheduler for a catering kitchen's prep tasks: a task can't start before its dependencies finish, higher-priority ready tasks jump the queue, and a dietary filter can remove tasks whose downstream dependents must then re-route around them. Tests topological ordering, deterministic tie-breaking, cycle handling, and precisely specifying filter-removal semantics.

A catering company's kitchen runs many prep tasks before an event (e.g. "make stock," "reduce sauce," "plate dish"). Implement a scheduler that decides a single valid order to run every task.

Each task has: an id, a list of deps (ids of tasks that must finish first), a numeric priority (higher runs sooner when more than one task is ready), and a set of tags describing what's in it (e.g. "nuts", "dairy", "shellfish").

Function Signature

def schedule(tasks: list[Task], exclude_tags: set[str] = ()) -> list[str]:

where Task has fields id: str, deps: list[str], priority: int, tags: set[str].

Rules

  • A task may appear in the output only after every task in its deps has already appeared.
  • Among tasks that are currently ready (all dependencies already scheduled), always schedule the one with the highest priority next. Ties break by the smaller id, for a fully deterministic order.
  • exclude_tags removes every task whose tags intersects it. A removed task never appears in the output. Any surviving task that depended on a removed task should depend instead on that removed task's own dependencies (transitively, until only surviving tasks remain) — removing a task does not strand its dependents, it splices around it.
  • A dependency cycle among surviving tasks is an error: raise ValueError naming the tasks involved.
  • A deps entry referencing an unknown task id is also an error: raise ValueError.

Example

tasks:
  stock   deps=[]             priority=5
  sauce   deps=[stock]        priority=7
  dough   deps=[]             priority=3
  pasta   deps=[dough]        priority=3
  plate   deps=[sauce, pasta] priority=9

schedule(tasks) -> ["stock", "sauce", "dough", "pasta", "plate"]

stock and dough are both ready at the start; stock has higher priority (5 > 3) so it goes first. That makes sauce ready (priority 7), which now outranks dough (3) even though dough has been ready longer, so sauce goes next. Then dough, then pasta, then plate once both its dependencies are done.

Part 1 — Dependencies and priority

Implement ordering with dependencies and the priority tie-break, ignoring exclude_tags (always empty).

Part 2 — Filtering with splicing

Add exclude_tags, including the re-routing rule: a kept task whose dependency was removed depends instead on that removed task's own (surviving, transitive) dependencies.

A straightforward topological sort (Kahn's algorithm) already tracks each task's remaining unmet dependency count; swap its FIFO queue of ready tasks for a priority structure keyed on (priority, id) and the tie-break falls out naturally.

Constraints

  • Up to 10^4 tasks.
  • priority values can repeat; ids are unique among surviving tasks.

Hints

Hint 1

Build the splice step (Part 2) before you build the ready-queue: compute each surviving task's final dependency list first, by recursively replacing any removed dependency with its own dependencies, then run ordering on that cleaned-up graph.

Hint 2

Use Kahn's algorithm: track an indegree per task and a children list per task (built from the cleaned-up dependency lists), seed a heap with every task starting at indegree 0.

Hint 3

Use a min-heap of (-priority, id) so popping gives you the highest priority, with ties broken by the smallest id automatically, since heapq compares tuples lexicographically.

Hint 4

Detect a cycle by comparing the number of tasks you managed to schedule against the number of surviving tasks — if they don't match, whatever's left with nonzero indegree is part of a cycle.

Follow-up questions

  • How would you change the output to stages of tasks that could all run in parallel, rather than one flat order?
  • If a high-priority task depends on a low-priority one, should the scheduler ever pull the dependency forward ahead of other already-ready tasks? Does your current design already do that correctly, or does it need a change?
  • How would you support multiple exclude_tags filters combined with OR instead of this single-set AND-style membership check?
  • How would you unit test cycle detection and the splice rule independently of each other?