Implement a Concurrent Payment Queue with Visibility Timeouts

Implement and explain an in-memory payment-message queue with this interface: ```java interface PaymentMessageQueue { void submit(PaymentMessage message); PaymentMessage receive(); void ack(String messageId); } ``` `submit` makes a message available. `receive` returns the next available message and hides it from other receives for a visibility timeout. An acknowledgment deletes the message. If it has not been acknowledged when its visibility period ends, it becomes available for redelivery. Use precise pseudocode or an implementation in a language with threads. Explain the synchronization and delivery semantics, including simultaneous consumers and ACK/timeout races. ### Constraints and Clarifying Questions - Several producers and consumers may call the queue concurrently within one process. Persistence across process failure is outside this in-memory contract. - Use a positive configurable visibility duration and a monotonic clock for elapsed-time decisions. An empty `receive` is nonblocking and returns no message. - State the assumptions about message-ID uniqueness and repeated submissions. - Clarify whether `ack(messageId)` represents completion of the logical message or must identify a particular delivery attempt. The given signature contains no delivery token. - Expiration makes redelivery eligible; discuss timer scheduling delay rather than promising a real-time dispatch deadline. ### Part 1 — Submit, Receive, and Acknowledge Define the queue's states and implement the three operations. Explain what happens when two consumers call `receive` at once and why simply peeking at a concurrent queue is insufficient. #### What This Part Should Cover - An atomic transition from available to in-flight, with an explicit visibility deadline. - A consistent relationship between the ready queue and in-flight tracking. - The chosen acknowledgment and duplicate-ID semantics. ### Part 2 — Expiration and Races Arrange redelivery without scanning every in-flight message on each receive. Explain the timeout callback, its race with `ack`, and what happens when an old callback runs after the message has been delivered again. #### What This Part Should Cover - A timer mechanism with bounded per-message bookkeeping and its scheduling costs. - A single winning state transition when acknowledgment and expiration compete. - Protection against stale callbacks and message resurrection. - Limits of an acknowledgment API that supplies only the message ID. ### Part 3 — Payment-Processing Guarantees Can this queue guarantee exactly-once processing? Explain a case where processing exceeds the visibility timeout and how the payment handler should tolerate repeated delivery. #### What This Part Should Cover - The difference between a current visibility lease and a consumer that is still doing work. - The queue's redelivery guarantee and the limitations of in-memory storage. - Idempotency at the boundary where payment effects are applied. ```hint Find the state transition A concurrent collection makes its own operations safe. Identify which multi-step changes across the ready queue, in-flight state, and timers must behave as one transition. ``` ### What a Strong Answer Covers - A complete operation design with identifiable atomic decisions and no lost message between states. - Timeout handling whose correctness survives delayed callbacks and redelivery. - An honest distinction between delivery, acknowledgment, and external payment effects. ### Follow-up Questions - Is conditional removal using the same message object sufficient after that object is delivered more than once? - What extra information would be needed for attempt-specific acknowledgments? - How would timer overload or shutdown affect the guarantees of this in-memory implementation?