Dependency order

A baseline repeatedly scans all unfinished tasks, searching for one whose prerequisites are complete. A chain of V tasks can require V scans of V tasks, plus dependency checks. Sorting the supplied names has no relationship to edge direction; [save, fetch] with fetch → save is a direct counterexample.

Store each task's outgoing neighbors and remaining indegree. Initialize a FIFO queue with zero-indegree tasks. Removing one represents completion: append it to the answer, decrement each dependent once, and enqueue newly zero counts.

each remaining indegree equals the number of prerequisites not yet emitted. Consequently every queued task is safe to emit. Every edge is removed once. If tasks remain when the queue empties, every remaining vertex has an incoming edge; repeatedly following predecessors in a finite graph must revisit a vertex. That establishes a cycle without confusing a cycle with a merely disconnected graph.

Time is O(V + E) including duplicate-edge processing, with E counting submitted edges. Auxiliary space is O(V + U), where U is unique edges, excluding the O(V) returned order. No recursion stack is required. A min-heap gives lexical choices at an additional O(V log V) cost.

Follow-up 1 — explain the failure. Add save → fetch. Predict which tasks still emit before inspecting the changed graph. The answer is metrics only. Kahn's remaining set identifies blocked tasks, not necessarily exactly cycle members; DFS colors and parent edges can extract one actual cycle.

Follow-up 2 — run tasks concurrently. Readiness still depends on indegree, but decrement after successful completion, not dispatch. A failure must block or explicitly cancel its dependents. Draw separate ready, running, and completed sets; worker capacity limits dispatch, while graph correctness limits eligibility.

A senior candidate proves cycle detection and tests disconnected/duplicate inputs. Lead depth adds ownership of cancellation and incremental plan changes; this local ordering function does not supply a distributed scheduler guarantee.

Reference: solution.py (download file, source below). Tests check edge order, duplicate normalization, partial cycles, invalid IDs, and a long chain.

"""Deterministic topological order with duplicate-edge normalization."""
from collections import deque


def dependency_order(tasks, dependencies):
    """dependencies contains (prerequisite, dependent); cycles raise ValueError."""
    tasks = list(tasks)
    if len(set(tasks)) != len(tasks):
        raise ValueError("duplicate task")
    dependents = {task: [] for task in tasks}
    remaining_prerequisites = dict.fromkeys(tasks, 0)
    unique_edges = set()
    for before, after in dependencies:
        if before not in dependents or after not in dependents:
            raise ValueError("unknown task")
        if (before, after) not in unique_edges:
            unique_edges.add((before, after))
            dependents[before].append(after)
            remaining_prerequisites[after] += 1
    ready = deque(task for task in tasks if remaining_prerequisites[task] == 0)
    result = []
    while ready:
        task = ready.popleft()
        result.append(task)
        for child in dependents[task]:
            remaining_prerequisites[child] -= 1
            if remaining_prerequisites[child] == 0:
                ready.append(child)
    if len(result) != len(tasks):
        raise ValueError("dependency cycle")
    return result

python -m unittest discover -s curriculum/01-code/02-data-structures-algorithms/problems/21-dependency-order -p 'test_*.py'