FoundationalProblem 12 of 20

FoundationalIntermediate

Printer Spooler

Strategy PatternState PatternObserver Pattern

Multi-printer queue with priorities and paper/toner constraints. A priority queue per printer plus a job router handles the routing; cancellation and retries handle the rest.

Key Abstractions

PrintJob

What to print — pages, copies, duplex, priority, submitting user

Printer

One physical device. Owns its queue, paper/toner state, and current job.

PrintQueue

Priority queue of jobs for a printer

JobRouter

Strategy picking which printer a new job goes to — round-robin, least-loaded, nearest

SpoolService

Facade. Submit, cancel, status. Manages printer pool and router.

Class Diagram

The Key Insight

The classic trap is one global queue feeding all printers. It sounds elegant but it's a coordination disaster: every printer contends on the same queue, a stalled printer holds jobs it can't finish, and fairness gets fuzzy fast. The real-world design — one queue per printer plus a router that picks on submit — decouples the printers completely. If printer 1 jams, printer 2 keeps going.

Priority isn't a feature to bolt on; it's in the data model. An enum gives compile-time safety (no priority = 47 weirdness) and a natural comparator. FIFO within a priority level keeps things fair — two HIGH jobs submitted in order print in order.

The consumable model (paper, toner) matters more than it looks. A printer with 3 sheets of paper and a 50-page job should reject the submission, not start printing and fail at page 3. Surfacing is_available gives the router a clean signal to route elsewhere, and an ops dashboard a clean signal to dispatch a refill tech.

Requirements

Functional

Submit jobs with document, copies, priority
Route to one of several printers based on policy
Cancel queued jobs (but not the currently printing one)
Track paper and toner; reject new jobs on low supplies
Support priority ordering and fair FIFO within a priority

Non-Functional

Printers process in parallel (one queue each)
Cancellation is O(log n) — flag-and-skip
Router strategy swappable (least-loaded, round-robin, nearest)
Status queryable by job ID

Design Decisions

Why per-printer queues?

One global queue creates a chokepoint. Per-printer queues let devices run independently — one printer's problem stays local. The router absorbs the "pick a printer" decision at submit time, which is the right moment to make it (we know current loads, user's office location, etc.).

Why Priority as an enum?

An integer priority tempts everyone to invent levels — 7, 9, 42 — and debugging why "priority 42 came before priority 40" wastes hours. Three enum values (HIGH, NORMAL, LOW) match how humans actually think about print urgency and stay readable in logs.

Why flag-and-skip for cancellation?

A priority queue doesn't support arbitrary-key removal efficiently. Marking a job as cancelled and dropping it on poll is O(1) to mark, O(1) amortized to skip. Cleaner than rebuilding the heap.

Why can't we cancel the currently-printing job?

The page is literally halfway through the rollers. "Cancelling" would mean ejecting a half-printed page — achievable but not worth the hardware complexity. Real spoolers model this: cancellation only affects jobs still in the queue.

Why separate JobRouter from SpoolService?

Router is a policy. Service is the machinery. A building with one printer per floor wants nearest-floor routing. A print shop wants least-loaded for throughput. Same SpoolService, different router — no forks or feature flags required.

Interview Follow-ups

"How would you support printer groups (color printers only, A3-capable only)?" Add capabilities: Set<Capability> to Printer and requires: Set<Capability> to PrintJob. Router filters by capability match first.
"What about user quotas (max 500 pages/month)?" Observer on job completion updates a per-user counter. Submit consults the counter before routing; quota exhaustion returns a clear error.
"How do you handle a jammed printer?" Printer state machine: READY → BUSY → JAMMED. Router skips JAMMED printers. Jam-clear event moves back to READY. Queued jobs stay in place; admins can rebalance.
"How would secure printing work?" Job marked requiresPin. Printer holds it in queue but doesn't auto-process. User enters PIN at the device; matched jobs release for that printer only.
"What if we add a print server cluster?" Each server node owns a subset of printers (sharding by printer ID). The SpoolService API sits behind a load balancer. Status lookups route via consistent hashing on job ID.

Code Implementation

from __future__ import annotations
from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from datetime import datetime
from enum import Enum
from threading import RLock
from typing import Callable
import heapq
import itertools
import uuid


class Priority(Enum):
    HIGH = 1
    NORMAL = 2
    LOW = 3


class JobStatus(Enum):
    QUEUED = "queued"
    PRINTING = "printing"
    DONE = "done"
    FAILED = "failed"
    CANCELLED = "cancelled"


@dataclass
class Document:
    name: str
    page_count: int


_seq = itertools.count()


@dataclass
class PrintJob:
    id: str
    user_id: str
    document: Document
    copies: int = 1
    duplex: bool = False
    priority: Priority = Priority.NORMAL
    status: JobStatus = JobStatus.QUEUED
    created_at: datetime = field(default_factory=datetime.utcnow)
    seq: int = field(default_factory=lambda: next(_seq))

    def total_pages(self) -> int:
        return self.copies * self.document.page_count

    def __lt__(self, other: "PrintJob") -> bool:
        # Lower priority enum value wins (HIGH=1 before NORMAL=2). FIFO tie-break.
        return (self.priority.value, self.seq) < (other.priority.value, other.seq)


class PrintQueue:
    def __init__(self):
        self._heap: list[PrintJob] = []
        self._index: dict[str, PrintJob] = {}
        self._lock = RLock()

    def offer(self, job: PrintJob) -> None:
        with self._lock:
            heapq.heappush(self._heap, job)
            self._index[job.id] = job

    def poll(self) -> PrintJob | None:
        with self._lock:
            while self._heap:
                candidate = heapq.heappop(self._heap)
                # Drop cancelled jobs silently.
                if candidate.status == JobStatus.CANCELLED:
                    self._index.pop(candidate.id, None)
                    continue
                self._index.pop(candidate.id, None)
                return candidate
            return None

    def size(self) -> int:
        with self._lock:
            return sum(1 for j in self._heap if j.status == JobStatus.QUEUED)

    def cancel(self, job_id: str) -> bool:
        with self._lock:
            job = self._index.get(job_id)
            if job is None or job.status != JobStatus.QUEUED:
                return False
            job.status = JobStatus.CANCELLED
            return True


class Printer:
    def __init__(self, printer_id: str, model: str, paper: int = 500, toner: int = 10_000):
        self.id = printer_id
        self.model = model
        self._queue = PrintQueue()
        self._paper = paper        # sheets available
        self._toner = toner        # arbitrary units
        self._current: PrintJob | None = None
        self._lock = RLock()

    @property
    def queue_size(self) -> int:
        return self._queue.size()

    @property
    def is_available(self) -> bool:
        # Available means "accepting jobs" — low supplies block new submissions.
        with self._lock:
            return self._paper > 10 and self._toner > 100

    def submit(self, job: PrintJob) -> None:
        if not self.is_available:
            raise RuntimeError(f"Printer {self.id} not accepting jobs — low supplies")
        self._queue.offer(job)

    def process_next(self) -> PrintJob | None:
        job = self._queue.poll()
        if job is None:
            return None
        with self._lock:
            self._current = job
            job.status = JobStatus.PRINTING
            pages_needed = job.total_pages()
            if self._paper < pages_needed:
                job.status = JobStatus.FAILED
                self._current = None
                return job
            # Simulate consumption.
            self._paper -= pages_needed
            self._toner -= pages_needed  # 1 toner unit per page — rough
            job.status = JobStatus.DONE
            self._current = None
            return job

    def refill_paper(self, sheets: int) -> None:
        with self._lock:
            self._paper += sheets

    def refill_toner(self, units: int) -> None:
        with self._lock:
            self._toner += units

    def cancel_queued(self, job_id: str) -> bool:
        return self._queue.cancel(job_id)


class JobRouter(ABC):
    @abstractmethod
    def pick(self, printers: list[Printer], job: PrintJob) -> Printer | None: ...


class LeastLoadedRouter(JobRouter):
    def pick(self, printers: list[Printer], job: PrintJob) -> Printer | None:
        eligible = [p for p in printers if p.is_available]
        return min(eligible, key=lambda p: p.queue_size) if eligible else None


class RoundRobinRouter(JobRouter):
    def __init__(self):
        self._cursor = 0
        self._lock = RLock()

    def pick(self, printers: list[Printer], job: PrintJob) -> Printer | None:
        eligible = [p for p in printers if p.is_available]
        if not eligible:
            return None
        with self._lock:
            idx = self._cursor % len(eligible)
            self._cursor += 1
            return eligible[idx]


class NotificationBus:
    """Observer bus. Events: submitted, started, completed, failed, cancelled."""

    def __init__(self):
        self._subs: list[Callable[[str, PrintJob], None]] = []

    def subscribe(self, handler: Callable[[str, PrintJob], None]) -> None:
        self._subs.append(handler)

    def publish(self, event: str, job: PrintJob) -> None:
        for h in self._subs:
            h(event, job)


class SpoolService:
    def __init__(self, printers: list[Printer], router: JobRouter | None = None):
        if not printers:
            raise ValueError("need at least one printer")
        self._printers = printers
        self._router = router or LeastLoadedRouter()
        self._jobs: dict[str, PrintJob] = {}
        self._job_to_printer: dict[str, str] = {}
        self._bus = NotificationBus()

    def subscribe(self, handler: Callable[[str, PrintJob], None]) -> None:
        self._bus.subscribe(handler)

    def submit(self, user_id: str, document: Document, copies: int = 1,
               priority: Priority = Priority.NORMAL, duplex: bool = False) -> str:
        if copies < 1:
            raise ValueError("copies must be >= 1")
        job = PrintJob(
            id=str(uuid.uuid4())[:8],
            user_id=user_id,
            document=document,
            copies=copies,
            duplex=duplex,
            priority=priority,
        )
        printer = self._router.pick(self._printers, job)
        if printer is None:
            raise RuntimeError("No printer available")
        printer.submit(job)
        self._jobs[job.id] = job
        self._job_to_printer[job.id] = printer.id
        self._bus.publish("submitted", job)
        return job.id

    def cancel(self, job_id: str) -> bool:
        printer_id = self._job_to_printer.get(job_id)
        if printer_id is None:
            return False
        printer = next(p for p in self._printers if p.id == printer_id)
        cancelled = printer.cancel_queued(job_id)
        if cancelled:
            self._bus.publish("cancelled", self._jobs[job_id])
        return cancelled

    def status(self, job_id: str) -> JobStatus | None:
        job = self._jobs.get(job_id)
        return job.status if job else None

    def run_once(self) -> int:
        """Each printer drains one job. Returns total processed."""
        processed = 0
        for printer in self._printers:
            job = printer.process_next()
            if job is None:
                continue
            processed += 1
            # printer.process_next already set status to DONE or FAILED.
            event = "completed" if job.status == JobStatus.DONE else "failed"
            self._bus.publish(event, job)
        return processed


if __name__ == "__main__":
    p1 = Printer("HP-01", "LaserJet", paper=100, toner=500)
    p2 = Printer("HP-02", "LaserJet", paper=100, toner=500)
    svc = SpoolService([p1, p2], router=LeastLoadedRouter())

    events: list[tuple[str, str]] = []
    svc.subscribe(lambda ev, job: events.append((ev, job.id)))

    ids = []
    for i in range(5):
        ids.append(svc.submit(f"user-{i}", Document(f"report-{i}.pdf", page_count=10)))
    high = svc.submit("urgent-user", Document("critical.pdf", page_count=2), priority=Priority.HIGH)
    ids.append(high)

    print(f"P1 queue: {p1.queue_size}, P2 queue: {p2.queue_size}")

    # Cancel one queued job.
    svc.cancel(ids[2])
    print(f"Cancelled {ids[2][:8]}, status = {svc.status(ids[2]).value}")

    # Drain queues. High-priority job goes first on whichever printer holds it.
    while svc.run_once() > 0:
        pass

    done = sum(1 for i in ids if svc.status(i) == JobStatus.DONE)
    cancelled = sum(1 for i in ids if svc.status(i) == JobStatus.CANCELLED)
    print(f"Completed: {done}, Cancelled: {cancelled}")
    print(f"Paper left — P1: {p1._paper}, P2: {p2._paper}")

    # Observer summary.
    counts: dict[str, int] = {}
    for ev, _ in events:
        counts[ev] = counts.get(ev, 0) + 1
    print(f"Events fired: {counts}")
    assert counts.get("submitted", 0) == len(ids)
    assert counts.get("completed", 0) == done
    assert counts.get("cancelled", 0) == cancelled

import java.time.Instant;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantLock;

enum Priority { HIGH(1), NORMAL(2), LOW(3); final int v; Priority(int v){this.v=v;} }
enum JobStatus { QUEUED, PRINTING, DONE, FAILED, CANCELLED }

class Document {
    final String name;
    final int pageCount;
    Document(String name, int pageCount) { this.name = name; this.pageCount = pageCount; }
}

class PrintJob implements Comparable<PrintJob> {
    private static final AtomicInteger SEQ = new AtomicInteger();
    final String id;
    final String userId;
    final Document document;
    final int copies;
    final boolean duplex;
    final Priority priority;
    final long seq;
    final Instant createdAt = Instant.now();
    volatile JobStatus status = JobStatus.QUEUED;

    PrintJob(String id, String userId, Document doc, int copies, boolean duplex, Priority priority) {
        this.id = id; this.userId = userId; this.document = doc;
        this.copies = copies; this.duplex = duplex; this.priority = priority;
        this.seq = SEQ.getAndIncrement();
    }

    int totalPages() { return copies * document.pageCount; }

    public int compareTo(PrintJob other) {
        int c = Integer.compare(priority.v, other.priority.v);
        return c != 0 ? c : Long.compare(seq, other.seq);
    }
}

class PrintQueue {
    private final PriorityQueue<PrintJob> heap = new PriorityQueue<>();
    private final Map<String, PrintJob> index = new HashMap<>();
    private final ReentrantLock lock = new ReentrantLock();

    void offer(PrintJob job) {
        lock.lock();
        try { heap.offer(job); index.put(job.id, job); } finally { lock.unlock(); }
    }

    PrintJob poll() {
        lock.lock();
        try {
            while (!heap.isEmpty()) {
                PrintJob j = heap.poll();
                index.remove(j.id);
                if (j.status == JobStatus.CANCELLED) continue;
                return j;
            }
            return null;
        } finally { lock.unlock(); }
    }

    int size() {
        lock.lock();
        try {
            int count = 0;
            for (PrintJob j : heap) if (j.status == JobStatus.QUEUED) count++;
            return count;
        } finally { lock.unlock(); }
    }

    boolean cancel(String id) {
        lock.lock();
        try {
            PrintJob j = index.get(id);
            if (j == null || j.status != JobStatus.QUEUED) return false;
            j.status = JobStatus.CANCELLED;
            return true;
        } finally { lock.unlock(); }
    }
}

class Printer {
    final String id, model;
    private final PrintQueue queue = new PrintQueue();
    private int paper, toner;
    private final ReentrantLock lock = new ReentrantLock();

    Printer(String id, String model, int paper, int toner) {
        this.id = id; this.model = model; this.paper = paper; this.toner = toner;
    }

    int queueSize() { return queue.size(); }

    boolean isAvailable() {
        lock.lock();
        try { return paper > 10 && toner > 100; } finally { lock.unlock(); }
    }

    void submit(PrintJob j) {
        if (!isAvailable()) throw new IllegalStateException("Supplies low on " + id);
        queue.offer(j);
    }

    PrintJob processNext() {
        PrintJob job = queue.poll();
        if (job == null) return null;
        lock.lock();
        try {
            job.status = JobStatus.PRINTING;
            int pages = job.totalPages();
            if (paper < pages) { job.status = JobStatus.FAILED; return job; }
            paper -= pages;
            toner -= pages;
            job.status = JobStatus.DONE;
            return job;
        } finally { lock.unlock(); }
    }

    boolean cancelQueued(String jobId) { return queue.cancel(jobId); }

    int getPaper() { return paper; }
}

interface JobRouter { Printer pick(List<Printer> printers, PrintJob job); }

class LeastLoadedRouter implements JobRouter {
    public Printer pick(List<Printer> printers, PrintJob job) {
        return printers.stream()
            .filter(Printer::isAvailable)
            .min(Comparator.comparingInt(Printer::queueSize))
            .orElse(null);
    }
}

public class SpoolService {
    private final List<Printer> printers;
    private final JobRouter router;
    private final Map<String, PrintJob> jobs = new HashMap<>();
    private final Map<String, String> jobToPrinter = new HashMap<>();
    private final List<java.util.function.BiConsumer<String, PrintJob>> subscribers = new ArrayList<>();

    public SpoolService(List<Printer> printers, JobRouter router) {
        if (printers.isEmpty()) throw new IllegalArgumentException("printers");
        this.printers = printers; this.router = router;
    }

    public void subscribe(java.util.function.BiConsumer<String, PrintJob> handler) {
        subscribers.add(handler);
    }

    private void publish(String event, PrintJob job) {
        for (var h : subscribers) h.accept(event, job);
    }

    public String submit(String userId, Document doc, int copies, Priority p) {
        PrintJob j = new PrintJob(UUID.randomUUID().toString().substring(0, 8),
            userId, doc, copies, false, p);
        Printer target = router.pick(printers, j);
        if (target == null) throw new IllegalStateException("No printer");
        target.submit(j);
        jobs.put(j.id, j);
        jobToPrinter.put(j.id, target.id);
        publish("submitted", j);
        return j.id;
    }

    public boolean cancel(String jobId) {
        String pid = jobToPrinter.get(jobId);
        if (pid == null) return false;
        Printer p = printers.stream().filter(x -> x.id.equals(pid)).findFirst().orElse(null);
        boolean ok = p != null && p.cancelQueued(jobId);
        if (ok) publish("cancelled", jobs.get(jobId));
        return ok;
    }

    public JobStatus status(String jobId) {
        PrintJob j = jobs.get(jobId);
        return j == null ? null : j.status;
    }

    public int runOnce() {
        int processed = 0;
        for (Printer p : printers) {
            PrintJob j = p.processNext();
            if (j == null) continue;
            processed++;
            publish(j.status == JobStatus.DONE ? "completed" : "failed", j);
        }
        return processed;
    }

    public static void main(String[] args) {
        Printer p1 = new Printer("HP-01", "LaserJet", 100, 500);
        Printer p2 = new Printer("HP-02", "LaserJet", 100, 500);
        SpoolService svc = new SpoolService(List.of(p1, p2), new LeastLoadedRouter());
        Map<String, Integer> counts = new HashMap<>();
        svc.subscribe((ev, job) -> counts.merge(ev, 1, Integer::sum));
        for (int i = 0; i < 5; i++)
            svc.submit("u" + i, new Document("r" + i + ".pdf", 10), 1, Priority.NORMAL);
        svc.submit("urgent", new Document("critical.pdf", 2), 1, Priority.HIGH);
        while (svc.runOnce() > 0) {}
        System.out.println("Paper left: P1=" + p1.getPaper() + " P2=" + p2.getPaper());
        System.out.println("Events: " + counts);
    }
}

Common Mistakes

✗Single global queue with all printers pulling. Heavy contention and unfair routing under load.
✗Cancellation that kills the currently-printing job. The sheet of paper is already halfway through — cancel only affects queued jobs.
✗Forgetting to decrement paper count per page. Printer runs empty and users see 'printing' with nothing coming out.
✗Priority as a float. Use an enum — HIGH, NORMAL, LOW. Comparable, predictable, debuggable.

Key Points

✓Priority queue per printer, not a global queue. Printers work in parallel.
✓Job state machine: QUEUED → PRINTING → DONE, or QUEUED → CANCELLED, or PRINTING → FAILED.
✓Paper/toner modeled as consumables. Low-supply state stops accepting jobs and surfaces an alert.
✓Router is a Strategy — round-robin for fairness, least-loaded for throughput, nearest for office floors.

Related Designs