Retrying job queue

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.
Call	Returns
`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.
Call	Returns
`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.
Call	Returns
`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.
Call	Returns
`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

Retry Queue Correctness: Duplicate Work, Retry Boundaries, and Cancellation

Solution guide

Reveal solution guide — spoilers

Approach

Store all accepted IDs in a permanent identity map, with each active job’s payload, state and latest attempt. Track active count separately from the waiting FIFO.
Reserve from the waiting head, mark the job in flight and increment that job’s attempt. Accept Ack or Retry only when both the in-flight state and attempt token match; Retry appends to the waiting tail without freeing capacity.
Ack and Cancel release an active capacity slot while retaining the accepted ID as a tombstone. Remove or skip cancelled waiting entries while preserving the order of remaining jobs. Keep every queue instance independent.

Why it works

The active counter includes both waiting and in-flight jobs, so reservation cannot create capacity. State plus attempt identity fences late acknowledgements from earlier reservations. Retaining accepted IDs prevents a completed job from being silently replaced, and appending retries preserves the specified FIFO order.

Complexity

With an ID map and a linked waiting queue, enqueue, reserve, acknowledge, retry and cancel use expected O(1) time. A simpler array/list implementation may need O(Q) removal or scanning. Storage is O(U) for U accepted IDs, including terminal tombstones.

Edge cases to check

Capacity zero rejects every enqueue. A full queue must not reserve a rejected ID, so enqueueing it after capacity frees can succeed.
An in-flight job occupies capacity even when Reserve returns no waiting job.
A stale attempt cannot acknowledge a retried reservation, and cancelled/completed IDs cannot be reused.

Restoring local drafts…

Retrying job queue

Retrying job queue

Your task

Required API

Behavior

Examples

Example 1 · fifo

Example 2 · retry fences old attempt

Example 3 · in flight capacity

Example 4 · cancel keeps id reserved

Related guides

Solution guide

Approach

Why it works

Complexity

Edge cases to check

Public examples

Explore the examples.