Design a Scheduler with Prerequisites and Target Execution Plans

Design a task scheduler in three stages: support addTask and getNextTask; add prerequisites and task completion; then return an execution plan for a requested target task. ### Clarifying Questions The task description does not specify scheduling priority, whether retrieval reserves a task, how unknown prerequisite IDs work, or whether an execution path means one chain or all required ancestors. Resolve these before implementing. For a concrete design discussion, choose unique IDs, prerequisites that already exist, retrieval that reserves the earliest-added ready task, and a plan containing every unfinished prerequisite needed to execute the target in a valid order. These are practice choices, not additional reported interview requirements. ### Part 1 — Add and Retrieve Tasks Define the task state and implement pseudocode for insertion and retrieval, including an empty scheduler. #### What This Part Should Cover Specify duplicate-ID handling, the ready queue, and the effect of retrieval on future retrievals. ### Part 2 — Prerequisites and Completion Extend the scheduler so a task becomes ready only after every prerequisite is complete. Define completeTask behavior. #### What This Part Should Cover Track remaining prerequisites and reverse dependency edges. Explain repeated completion, invalid completion, and tasks that are not yet runnable. ### Part 3 — Plan for a Target Given a target ID, return its unfinished prerequisite tasks followed by the target, in an order that respects dependencies. Explain what happens if a required task is already running. #### What This Part Should Cover Traverse only the target's dependency closure, avoid duplicates at shared prerequisites, and distinguish planning from claiming or executing work. ### What a Strong Answer Covers A coherent state machine across all three stages, clear operation semantics, concrete pseudocode, complexity, and examples that exercise blocked and shared dependencies. ### Follow-up Questions - How would allowing dependencies on not-yet-added IDs change cycle detection? - What synchronization is required if multiple workers call getNextTask concurrently?