Design a Bounded Blocking Queue

Hard·Tagsllddesignconcurrencyblocking-queuewait-notify

Problem Statement

Design a thread-safe bounded blocking queue. `put` blocks the calling thread when the queue is full; `take` blocks when it is empty; both wake up as soon as the other side makes the queue ready. This is the classic concurrency exercise. The expected implementation uses `synchronized` + `wait()`/`notifyAll()` (or `ReentrantLock` + two `Condition`s — `notFull` and `notEmpty`). FIFO ordering must be preserved across threads. API contract ```java class BoundedBlockingQueue<T> { public BoundedBlockingQueue(int capacity); // capacity > 0; throws otherwise /** Insert an item at the tail. Blocks until space is available or the thread is * interrupted (re-throws InterruptedException). */ public void put(T item) throws InterruptedException; /** Remove and return the head item. Blocks until an item is available or the thread is * interrupted (re-throws InterruptedException). */ public T take() throws InterruptedException; public int size(); } ``` The validator runs three checks: 1. *single_thread_put_take_fifo* — capacity 3, single thread: `put(1)`, `put(2)`, `put(3)`; `take()` returns 1, 2, 3 in order; sizes and FIFO behaviour are correct. 2. *producer_consumer_delivers_all* — capacity 5; one producer thread puts integers 1..50; one consumer thread takes 50 items. After both finish (`CountDownLatch.await(5, SECONDS)`): exactly 50 items received, all unique, queue empty. The capacity 5 forces the producer to block multiple times — if `put` did not block, items would be lost or the queue would exceed capacity. 3. *capacity_enforces_blocking* — capacity 3, producer tries to put 8 items, no consumer running. After a brief settle period the queue size must be exactly 3 (not >3). Then start a consumer; all 8 items must eventually be received. The stub class throws `UnsupportedOperationException` from every method. *Test budget:* the validator uses `await(5, SECONDS)` for bounded waits. A correct implementation finishes each scenario in ~50–500ms; the 5-second budget is the loud-failure ceiling for deadlocks or missed signals.

Examples

Example 1

Input

var q = new BoundedBlockingQueue<Integer>(3); q.put(1); q.put(2); q.take()

Output

"1"

Why

FIFO. Inserted 1 then 2; first take returns 1.

Example 2

Input

Producer thread puts 1..50, consumer thread takes 50 items (capacity=5)

Output

"all 50 items delivered, no duplicates, no losses"

Why

Capacity 5 forces blocking; correct synchronization delivers every item exactly once.

Example 3

Input

capacity=3, producer attempts to put 8 items with no consumer running

Output

"queue size never exceeds 3"

Why

put() must block when the queue is full; size cannot grow past capacity.

Constraints

•Constructor: BoundedBlockingQueue(int capacity). capacity > 0; throws IllegalArgumentException otherwise.
•put blocks until space is available; take blocks until an item is available. Both re-throw InterruptedException.
•FIFO ordering: take() returns items in the order put() inserted them, even across multiple threads.
•Thread-safe: concurrent put() and take() from many threads must not corrupt state.
•size() must be safe to call from any thread; it returns the current size at the moment of the call.

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

The textbook implementation: an internal ArrayDeque<T>, a final int capacity, and `synchronized` methods that use `wait()` / `notifyAll()` on `this`.

Hint 2

Always wrap `wait()` in a while-loop checking the predicate (queue full / queue empty). `if` is a classic bug — spurious wake-ups and re-acquired locks can leave the predicate false again.

Hint 3

`put`: while (size == capacity) wait(); add(item); notifyAll(). `take`: while (size == 0) wait(); poll(); notifyAll(). notifyAll is safer than notify when both producers and consumers may be waiting.

Hint 4

Re-throw InterruptedException — do not swallow it. The contract says callers can interrupt blocked threads; swallowing breaks cancellation.

Hint 5

Mark size() as synchronized (or use volatile counters) so concurrent reads see consistent state. Returning a stale value is a bug under concurrent access.