Katkat
Back

Print Shop Job Queue: Retries, a Poison Queue and Job Prerequisites

OpenAISoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Implement an in-memory job queue for a print shop where workers reserve, complete, or fail jobs, failed jobs retry up to a limit before landing in a poison queue, and a second part adds job prerequisites with cascading failure.

A print shop runs print jobs (flyers, booklets, posters) through machines that occasionally jam. Build the in-memory queue that hands jobs to workers, retries jams up to a limit, and quarantines jobs that keep failing. Unit tests must pass against this interface (adjust names only after confirming with the interviewer):

class PrintJobQueue:
    def __init__(self, max_attempts: int): ...
    def submit(self, job_id: str, payload: object, depends_on: list[str] | None = None) -> None: ...
    def reserve(self) -> tuple[str, object] | None: ...
    def complete(self, job_id: str) -> None: ...
    def fail(self, job_id: str) -> None: ...
    def dead_letters(self) -> list[str]: ...

Clarify first

  • Does max_attempts = 3 mean the 3rd failure or the 4th sends a job to the poison queue?
  • When a job is retried, does it go to the back of the queue or stay at the front?
  • What does reserve() return when nothing is ready?
  • Can submit reference a depends_on job ID that hasn't been submitted yet?

Part 1 — Retries and the poison queue

Implement submit, reserve, complete, fail, and dead_letters. A job starts at 0 attempts. Each fail increments its attempt count; below max_attempts it goes back to the end of the queue for another reserve, at or above max_attempts it moves permanently to the poison queue (dead_letters(), in the order jobs were poisoned) and is never handed out again.

Part 2 — Job prerequisites

Add depends_on: a job only becomes eligible for reserve() once every job it depends on has completed. If a prerequisite ends up in the poison queue, the dependent job should be poisoned too — it can now never succeed, and should say so immediately rather than sitting blocked forever, and this must cascade through chains of dependencies.

Example

q = PrintJobQueue(max_attempts=2)
q.submit("cover", "cover page")
q.submit("bind", "bind booklet", depends_on=["cover"])
q.reserve()                  # -> ("cover", "cover page")  (bind is still blocked)
q.fail("cover")              # attempt 1 < 2, retried
q.reserve()                  # -> ("cover", "cover page") again
q.fail("cover")              # attempt 2 >= 2, poisoned
q.dead_letters()             # -> ["cover", "bind"]       (cascaded)
q.reserve()                  # -> None

Hints

Hint 1

Give every job a status (blocked, ready, reserved, done, poison) and model each operation as a transition out of exactly one expected status; reject or raise on anything else.

Hint 2

Track each job's unresolved dependency count. A job enters the ready queue the moment that count hits zero, whether that's at submit time (no deps) or after a dependency completes.

Hint 3

For the poison queue, do the cascade eagerly and recursively through a job's dependents, but let reserve() lazily skip queue entries whose status changed since they were enqueued, rather than removing them from the middle of the queue.

Hint 4

Decide what happens to a job submitted with a depends_on that's already poisoned — it should be poisoned immediately rather than ever reaching the ready queue.

Follow-up questions

  • How would you add a visibility timeout so a worker that reserves a job and then crashes doesn't hold it forever?
  • What changes if the same job_id can be safely re-submitted (idempotent submit) instead of raising on a duplicate?
  • How would you support canceling a job that has dependents, without leaving those dependents blocked forever?
  • If workers run in separate processes sharing this queue, what needs to change to make reserve/complete/fail safe under concurrent access?