Katkat
Back

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

CubistSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Design and implement a job tracker class that accepts job submissions with dependencies, hands out jobs that are ready to run, and reports each job's status. It tests state-machine design, dependency-graph bookkeeping, handling of failures and cycles, and thread safety when several workers call the class at once.

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.

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?

Hints

Hint 1

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 2

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 3

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.

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?