# Return a Valid Dependency Order for Named Tasks You are given a map from a task name to the list of tasks it depends on. Return an order in which every task appears after all of its dependencies. Tasks that appear only in dependency lists are still part of the graph. For deterministic grading, whenever several tasks are currently eligible, choose the lexicographically smallest task name. Return an empty list if the dependency graph contains a cycle. Example input: ```text { "Task1": ["Task0"], "Task3": ["Task0", "Task1", "Task2"], "Task2": ["Task0"] } ``` A valid order must place `Task0` before `Task1` and `Task2`, and must place all three before `Task3`. ### Constraints & Assumptions - Task names are strings and comparison for deterministic ordering is lexicographic. - Duplicate dependency names for one task do not create multiple logical edges. - The input map must not be mutated. ### Clarifying Questions to Ask - Should dependency-only names be included in the returned order? - What result should signal that not all tasks can be completed because of a cycle? - Is any valid ordering acceptable, or is deterministic tie-breaking required? ```hint Direct each edge toward its dependent If task `B` depends on task `A`, completing `A` should reduce the remaining prerequisite count for `B`. ``` ```hint Make the ready set deterministic Kahn's algorithm supplies zero-indegree tasks; the data structure used for that set determines which valid order is returned. ``` ### Evaluation Criteria - Construction of the full vertex set from both map keys and dependency values. - Correct indegree counts and reverse adjacency for Kahn's algorithm. - Lexicographically deterministic selection among ready tasks. - Cycle detection by comparing the returned count with the number of vertices. - Time complexity of `O(V + E + V log V)` with a heap-based ready set and `O(V + E)` storage. ### Extensions to Discuss - How would you change the result if the caller only needs to know whether every task is completable? - What is the complexity when any valid order is acceptable and a queue replaces the heap? - How would you return one concrete cycle for diagnostics?