Beyond Big O

Retrying job queue

Retrying job queue

Medium

Your task

  • Build a single-owner job queue for a small background worker.
  • Jobs wait in FIFO order.
  • A worker reserves a job, then either acknowledges success or returns it for retry.

Required API

  • NewQueue
    func NewQueue(capacity int) *Queue
  • Queue.Enqueue
    func (q *Queue) Enqueue(id, payload string) bool
  • Queue.Reserve
    func (q *Queue) Reserve() (Job, bool)
  • Queue.Ack
    func (q *Queue) Ack(id string, attempt int) bool
  • Queue.Retry
    func (q *Queue) Retry(id string, attempt int) bool
  • Queue.Cancel
    func (q *Queue) Cancel(id string) bool
  • Job.ID
    ID string
  • Job.Payload
    Payload string
  • Job.Attempt
    Attempt int

Behavior

  • Enqueue accepts a new ID and payload when the queue has room, appends it to the waiting tail, and returns true.
  • Reject a duplicate ID or a full queue with false and no changes.
  • Capacity counts all active jobs: both waiting and in flight.
  • Reserving a job does not free capacity.
  • An acknowledged or cancelled job frees capacity, but its ID stays reserved for the lifetime of that queue.
  • A rejected enqueue does not reserve its ID.
  • Reserve removes the oldest waiting job and marks it in flight.
  • Return its ID, original payload, and attempt number.
  • Each job's first reservation has attempt 1; every later reservation after retry increases that job's number by one.
  • Return an explicit missing result if no waiting job exists, even if other jobs are in flight.
  • Ack and Retry succeed only for an in-flight job with the exact current attempt number.
  • Ack completes the job.
  • Retry keeps its capacity slot and appends the job to the waiting tail; the next Reserve assigns its next attempt.
  • Unknown IDs, stale or future attempts, repeated operations and operations on waiting or completed jobs return false without changing state.
  • Attempt 0 is always invalid.
  • Cancel returns true for an active waiting or in-flight job, removes it immediately, and invalidates any reservation.
  • Cancellation must preserve the FIFO order of the remaining waiting jobs.
  • Unknown or already-finished IDs return false.
  • Separate queues must not share state.
  • Capacity is 0–16.
  • Each scenario has 0–64 operations and creates at most 8 queues with the same capacity.
  • IDs are valid, case-sensitive ASCII identifiers matching [A-Za-z0-9_-], length 1–16.
  • Payloads are printable ASCII strings, length 0–32, including empty strings.
  • Attempt arguments are integers 0–64.
  • Use only the standard library.
  • Actual threads, clocks, network calls and automatic retries are outside this exercise.
Notes and example notation
  • Examples encode operations as ["enqueue", id, payload], ["reserve"], ["ack", id, attempt], ["retry", id, attempt] or ["cancel", id].
  • Each output position corresponds to one operation: booleans for mutations, [id, payload, attempt] for a reservation, or null when no job is waiting.
  • The harness also uses ["new"] to create and select another queue and ["use", index] to select an earlier queue; both produce null.

Examples

The runner calls your functions directly; you do not need to parse JSON.

Example 1 · fifo

Calls in order; values are shown as data.
CallReturns
NewQueue(2)
Instance 1
instance1.Enqueue("a", "A")
true
instance1.Enqueue("b", "B")
true
instance1.Reserve()
Job snapshot
ID: "a"
Payload: "A"
Attempt: 1
found: true
instance1.Reserve()
Job snapshot
ID: "b"
Payload: "B"
Attempt: 1
found: true
instance1.Reserve()
Missing (found = false)
instance1.Ack("a", 1)
true
instance1.Ack("b", 1)
true
Test data
Input
{"capacity":2,"ops":[["enqueue","a","A"],["enqueue","b","B"],["reserve"],["reserve"],["reserve"],["ack","a",1],["ack","b",1]]}
Expected output
[true,true,["a","A",1],["b","B",1],null,true,true]

Example 2 · retry fences old attempt

Calls in order; values are shown as data.
CallReturns
NewQueue(1)
Instance 1
instance1.Enqueue("a", "A")
true
instance1.Reserve()
Job snapshot
ID: "a"
Payload: "A"
Attempt: 1
found: true
instance1.Retry("a", 1)
true
instance1.Reserve()
Job snapshot
ID: "a"
Payload: "A"
Attempt: 2
found: true
instance1.Ack("a", 1)
false
instance1.Retry("a", 1)
false
instance1.Ack("a", 2)
true
Test data
Input
{"capacity":1,"ops":[["enqueue","a","A"],["reserve"],["retry","a",1],["reserve"],["ack","a",1],["retry","a",1],["ack","a",2]]}
Expected output
[true,["a","A",1],true,["a","A",2],false,false,true]

Example 3 · in flight capacity

Calls in order; values are shown as data.
CallReturns
NewQueue(1)
Instance 1
instance1.Enqueue("a", "A")
true
instance1.Reserve()
Job snapshot
ID: "a"
Payload: "A"
Attempt: 1
found: true
instance1.Enqueue("b", "B")
false
instance1.Ack("a", 1)
true
instance1.Enqueue("b", "B")
true
instance1.Reserve()
Job snapshot
ID: "b"
Payload: "B"
Attempt: 1
found: true
Test data
Input
{"capacity":1,"ops":[["enqueue","a","A"],["reserve"],["enqueue","b","B"],["ack","a",1],["enqueue","b","B"],["reserve"]]}
Expected output
[true,["a","A",1],false,true,true,["b","B",1]]

Example 4 · cancel keeps id reserved

Calls in order; values are shown as data.
CallReturns
NewQueue(2)
Instance 1
instance1.Enqueue("a", "A")
true
instance1.Enqueue("b", "B")
true
instance1.Cancel("a")
true
instance1.Enqueue("a", "replacement")
false
instance1.Reserve()
Job snapshot
ID: "b"
Payload: "B"
Attempt: 1
found: true
instance1.Cancel("b")
true
instance1.Ack("b", 1)
false
instance1.Reserve()
Missing (found = false)
Test data
Input
{"capacity":2,"ops":[["enqueue","a","A"],["enqueue","b","B"],["cancel","a"],["enqueue","a","replacement"],["reserve"],["cancel","b"],["ack","b",1],["reserve"]]}
Expected output
[true,true,true,false,["b","B",1],true,false,null]

Related guides

Editor options
Typing preferences

Saved in this browser.

Restoring local drafts…