Design a class to submit jobs with dependencies and track their status

Design and implement a class that lets callers submit jobs and track the status of each job. A job can depend on other jobs: it must not start until every job it depends on has finished successfully. Write the class and its main methods, then explain how it behaves as jobs start, finish and fail. A reasonable starting API, which you may change after clarifying: - `submit(job_id, dependencies)` registers a job together with the ids of the jobs it depends on. - `get_status(job_id)` returns the job's current status. - A way for workers to obtain a job that is ready to run, and to report that it succeeded or failed. ```hint Name the states first Write down every status a job can be in, and the event that moves it from one status to the next, before you write any methods. A dependency failing is one of those events. ``` ```hint Only some jobs can change When a job finishes, only a few other jobs can possibly become runnable. Find a way to reach exactly those jobs and to tell cheaply whether each of them is now unblocked, instead of rechecking every waiting job. ``` ```hint A job that can never start Think about what a new job's dependency list could contain that would leave it, or other jobs, waiting forever. ``` ### Constraints and Clarifications - Job ids are unique strings. - The class tracks jobs; whether it also executes them is a question to settle with the interviewer. - Start with a single-threaded design, then explain what changes when several workers call the class at the same time. ### Clarifying Questions - Can a job be submitted before the jobs it depends on, and what happens if a dependency id is never submitted? - When a dependency fails, should its dependents fail as well, stay blocked until it is retried, or run anyway? - Does the class run jobs itself, or do external workers pick up runnable jobs and report the result? - Must the class reject a submission that would create a dependency cycle? - Can jobs be retried or cancelled, and are finished jobs ever removed? ### What a Strong Answer Covers - A clear status lifecycle, with the transition each method causes - Data structures that find newly runnable jobs without scanning all waiting jobs - Explicit handling of duplicate ids, unknown dependencies, cycles, and dependencies that already finished or failed - The time complexity of each method and the memory used - Behavior under concurrent calls, including how two workers are prevented from starting the same job ### Follow-up Questions - Several worker threads call the class concurrently. What do you lock, and how do you keep two workers from starting the same job? - How would you support cancelling a job, and what happens to the jobs that depend on it? - The tracker must survive a process restart. What do you persist, and what do you do with jobs that were running when it stopped? - How would you add retries with a maximum number of attempts without disturbing the status of dependent jobs?