Quant Memo
Coding/●●●●

Topological order for a job DAG

Asked at Two Sigma, DE Shaw

Your overnight batch runs pricing jobs with dependencies: ("curves", "swaps") means curves must finish before swaps starts.

jobs = ["curves", "vols", "swaps", "options", "risk"]
deps = [("curves", "swaps"), ("curves", "options"),
        ("vols", "options"), ("swaps", "risk"), ("options", "risk")]
-> ["curves", "vols", "swaps", "options", "risk"]   (one valid order)

Return any execution order respecting all dependencies, or None if the dependencies are cyclic. Aim for O(V+E)O(V + E).

Your answer

This one is open-ended. Work it through, then check your reasoning against the full solution.

More Coding questions