Implement a Thread-Safe Bounded Blocking Queue

Problem and When It Applies

Implement BoundedBlockingQueue<E>. Its constructor accepts a positive capacity. put(item) appends in FIFO order and waits while the queue is full. take() removes from the head and waits while the queue is empty. Multiple producers and consumers may call both methods concurrently. No element may be lost, returned twice, or returned after an element that entered earlier. If a thread is interrupted while acquiring the lock or waiting on a condition, the method throws InterruptedException.

The exercise does not allow wrapping ArrayBlockingQueue. The base API excludes nonblocking offer/poll, timeouts, bulk removal, and shutdown semantics, and it does not promise strict fairness among waiting threads. Those are follow-ups. Like Java's BlockingQueue, this implementation rejects null, because queue APIs often use null to mean that no element is available.

This is a concurrent data-structure coding problem. Array indexing is the easy part. The real test is whether the candidate can state an auditable contract: which synchronization protects the shared state, why notifications cannot be lost, why a woken thread must recheck its condition, and at what instant an operation takes effect for other threads.

What the Interviewer Is Evaluating

The first signal is whether the candidate separates safety from liveness. Safety requires the size to remain in [0, capacity], each element to be removed at most once, and removal order to match insertion order. Liveness requires a producer to get a chance to proceed when a full queue becomes nonfull and a consumer to get a chance when an empty queue becomes nonempty. Interruption must also be able to cancel a wait.

The second signal is whether synchronization primitives correspond to state predicates. One lock protects the array, head, tail, and size, so checking a condition and changing state occur in the same critical section. notFull represents size < capacity; notEmpty represents size > 0. Producers wait only for the former, consumers only for the latter, and a boundary-crossing state change signals the opposite role.

The third signal is whether the candidate can explain while instead of using it as a memorized pattern. Condition permits spurious wakeups. Even after a real signal, another competing thread may reacquire the lock first and fill or drain the queue again. Once the woken thread reacquires the lock, it must retest the predicate. Being notified does not prove the condition still holds.

Finally, the interviewer can probe the design: how the ring indices preserve FIFO, why the size update belongs to the linearization point, why one lock avoids lock-order deadlock, when signal is enough, and why timeouts and shutdown require new API semantics.

Questions to Clarify Before Answering

• Which capacities and elements are valid? Capacity must be greater than zero, and null elements are rejected.
• Should full or empty waits spin? No. A waiting thread must release the lock and wait on a condition. It must neither consume CPU in a spin loop nor sleep while retaining the lock.
• How should interruption behave? Both put and take propagate InterruptedException. They do not swallow interruption or change the queue after the interrupted operation fails.
• Is strict fairness required? Not in the base problem. The default nonfair ReentrantLock may let a later thread acquire the lock first. A fair lock changes throughput and scheduling behavior.
• Does the queue need shutdown? Not in the base problem. If it does, define whether existing items may drain, whether waiters receive an exception or a special result, and who wakes all waiters.
• Are linearized element FIFO and waiter FIFO the same guarantee? No. Elements leave in the linearization order of successful puts. That does not mean blocked producers or consumers are admitted in arrival order.
• May a standard library class be used? Production code should normally prefer a tested ArrayBlockingQueue. Hand implementation here is specifically for evaluating concurrency invariants and condition-wait semantics.

30-Second Answer Framework

“I will use a fixed array as a ring buffer, with head, tail, and size representing the next read position, next write position, and current element count. One ReentrantLock protects all shared state, and two Condition objects represent nonempty and nonfull. put waits inside while (size == capacity), inserts and increments size, then signals one consumer. take symmetrically waits for nonempty, clears the head and decrements size, then signals one producer. Every check and transition happens under the same lock. Because await atomically releases the lock and reacquires it before returning, there is no lost-notification window between checking and sleeping. Each successful operation is O(1), with O(capacity) space.”

Step-by-Step Deep Dive

Derive the representation from the naive bottleneck. A plain array that shifts remaining elements after every removal makes take O(n). Keeping a read index that only grows wastes the released prefix instead. A fixed ring array reuses released slots: head points to the next read position, tail points to the next write position, and size is the current element count. An index wraps to zero after reaching the end, so neither insertion nor removal shifts existing elements.

The implementation maintains four invariants:

1. 0 <= size <= items.length.
2. Starting at head, the first size slots in ring order contain the unconsumed FIFO sequence.
3. tail == (head + size) % items.length. When the queue is full, head == tail, so size distinguishes full from empty.
4. Every read or write of items, head, tail, and size occurs while holding the same lock.

Here is the core implementation:

import java.util.Objects;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

public final class BoundedBlockingQueue<E> {
  private final Object[] items;
  private final ReentrantLock lock = new ReentrantLock();
  private final Condition notEmpty = lock.newCondition();
  private final Condition notFull = lock.newCondition();

  private int head;
  private int tail;
  private int size;

  public BoundedBlockingQueue(int capacity) {
    if (capacity <= 0) {
      throw new IllegalArgumentException("capacity must be positive");
    }
    items = new Object[capacity];
  }

  public void put(E item) throws InterruptedException {
    Objects.requireNonNull(item, "item");
    lock.lockInterruptibly();
    try {
      while (size == items.length) {
        notFull.await();
      }

      items[tail] = item;
      tail = (tail + 1) % items.length;
      size++;
      notEmpty.signal();
    } finally {
      lock.unlock();
    }
  }

  @SuppressWarnings("unchecked")
  public E take() throws InterruptedException {
    lock.lockInterruptibly();
    try {
      while (size == 0) {
        notEmpty.await();
      }

      E item = (E) items[head];
      items[head] = null;
      head = (head + 1) % items.length;
      size--;
      notFull.signal();
      return item;
    } finally {
      lock.unlock();
    }
  }
}

Objects.requireNonNull runs before locking because it checks only an argument and does not depend on shared state. lockInterruptibly() makes waiting to acquire the lock itself interruptible. After the method enters try, finally releases the lock held by the current thread on normal return, interruption during a condition wait, or a runtime exception.

The essential await() guarantee is that it atomically releases the associated lock and waits, then reacquires that lock before returning. A producer must not unlock manually and only then register itself as a waiter. That creates a window in which a consumer can free space and send a notification before the producer has actually started waiting, losing the notification permanently. A condition variable combines “release and begin waiting” into one synchronization action and closes that window.

The while handles two different cases. One is the spurious wakeup permitted by the specification. The other is ordinary competition: two consumers may be awakened, one reacquires the lock first and removes the only element, and the second finds an empty queue when it finally gets the lock. A condition notification only says that state may have changed; the state predicate is the authority for proceeding.

The linearization point of a successful put is the locked transition that adds the element and moves size from k to k + 1. For take, it is the corresponding removal and transition from k to k - 1. The lock ensures another thread can observe either the complete state before the transition or the complete state after it, never an array write without its matching size update. Unlocking and subsequently acquiring the same lock also establishes memory visibility, matching the happens-before goal specified for passing elements through standard concurrent queues.

Why use two conditions? With one waiting set, a take might wake another consumer even though the queue remains empty, while a producer that could use the new slot stays asleep. Separating notEmpty and notFull lets each transition notify only the role that may now proceed. A base single-element put or take creates only one new element or slot, so signal() is sufficient; the woken thread still rechecks in a while. If one operation changes multiple slots, or shutdown requires every waiter to observe a new state, reconsider signalAll().

Correctness follows by induction on the invariants. Initially, head = tail = size = 0. An insertion runs only when size < capacity; it writes at tail, advances the tail, and increments size exactly once, so it stays within capacity and appends after all unconsumed elements. A removal runs only when size > 0; it reads at head, clears the slot, advances the head, and decrements size exactly once, so it returns the earliest unconsumed element. The lock serializes these transitions, making every schedule of many producers and consumers equivalent to some legal sequential execution.

Each successful put or take performs a fixed number of array, integer, and synchronization operations, so its work is O(1) excluding wait time. The fixed array uses O(capacity) space. Under contention, lock waiting and context switches can dominate latency; asymptotic notation does not capture that cost. A one-lock design has no multi-lock cycle, but callers can still create a larger lock-order problem if they invoke a blocking method while holding some other lock.

Testing cannot stop at a single-threaded example. Cover capacity-one full/empty alternation, multiple ring wraparounds, equal repeated elements being stored and removed separately, an empty string being accepted while null is rejected, unique values produced by several producers and drained by several consumers, no missing or duplicate values in the final set, preserved order within each individual producer stream, and interruption of both a blocked put and a blocked take. A huge capacity allocates an equally large array in the constructor and may fail for lack of memory; the base implementation is not lazy and must not disguise allocation failure as an empty queue. Concurrent tests should coordinate starts with a barrier or latch and use a test-runner deadline to detect permanent blocking. A short sleep is not proof that a thread reached its wait state.

High-Quality Sample Answer

“I would first scope the base contract to positive capacity, non-null elements, blocking put/take, FIFO, multiple producers and consumers, and interruptible waits. Timeouts, shutdown, and strict fairness need additional return values and state semantics, so I would keep them out of the core implementation.

The representation is a fixed ring array. head is the next read position, tail the next write position, and size removes the full-versus-empty ambiguity when head == tail. One ReentrantLock protects all four shared fields. The predicate for notEmpty is size > 0, and the predicate for notFull is size < capacity.

put acquires the lock interruptibly, waits for nonfull inside a while, writes at the tail and increments size, then signals one consumer. take symmetrically waits for nonempty, removes the head, clears the reference and decrements size, then signals one producer. The loop is required because condition waits may wake spuriously and because another thread may make the predicate false again while the woken thread is competing to reacquire the lock.

await atomically releases the lock and begins waiting, which avoids losing a notification after checking but before sleeping. The linearization point of a successful operation is the locked state transition that changes queue membership and size. The same lock means other threads see a complete before-state or after-state. Induction over the capacity, ring FIFO, and same-lock invariants proves that the implementation does not overflow, duplicate removals, or reorder elements.

Excluding blocking time, both methods are O(1), and space is O(capacity). I would start multiple producers and consumers with a latch, verify the set of unique identifiers and per-producer order, and separately test full, empty, and interruption paths.”

Common Mistakes

• Checking full or empty with if → the condition may still be false after a spurious wakeup or lock competition → retest the state predicate in a while.
• Unlocking manually after the check and then waiting → a state change can occur before waiter registration, losing the notification → use Condition.await() associated with the same lock.
• Synchronizing the array, indices, and size separately → another thread can observe a contradictory intermediate state → protect the entire check and transition with one lock.
• Using one wait set with an arbitrary signal → the signal may wake a same-role thread that cannot progress → maintain separate notEmpty and notFull conditions.
• Spinning or sleeping while holding the lock → the thread that could change the condition cannot acquire it → a condition wait must release the lock.
• Swallowing InterruptedException → callers cannot cancel work and the thread may remain indefinitely → declare and propagate interruption, and unlock in finally.
• Using only head == tail to detect both states → full and empty ring states are indistinguishable → maintain a lock-protected size.
• Leaving the removed reference in the array → the array retains a consumed object longer than necessary → set the slot to null after reading it.
• Equating element FIFO with thread fairness → the default lock does not complete waiting calls in arrival order → describe element ordering and scheduling policy separately.
• Claiming shutdown support in the base implementation → waiters have no observable closed state and may never wake → define the shutdown contract before adding state and broadcast notification.

Follow-Up Questions and Responses

Follow-up 1: How would you add timed offer and poll?

Convert the remaining duration to nanoseconds and call awaitNanos(remaining) inside the same predicate while loop. After every return, continue with the remaining time it reports. If the value is nonpositive and the predicate is still false, return failure. Reusing the full timeout after every spurious wakeup could extend the actual wait indefinitely. The API must also distinguish timeout from a null element, another reason to reject null.

Follow-up 2: How would you implement shutdown()?

Define the state machine first. For example, reject new puts after closure but allow existing items to drain; when closed and empty, take throws a dedicated exception or returns an explicit result. shutdown must change the closed flag under the same lock and call signalAll() on both conditions so every waiter can reacquire the lock and observe closure. Every wait-loop predicate needs a closed-state branch; adding only a boolean field is insufficient.

Follow-up 3: Why use signal() here, and when would you use signalAll()?

One base insertion creates one consumable element, and one removal creates one free slot. Waking one opposite-role thread is enough to make progress and reduces futile competition. Bulk insertion, bulk removal, dynamic capacity changes, or shutdown can make several waiters eligible at once, so they typically need signalAll() or a notification count matching the state change. Regardless of the number awakened, the while recheck remains mandatory.

Follow-up 4: How would you provide fairness?

new ReentrantLock(true) makes lock acquisition favor the longest-waiting thread, but it still does not provide an absolute real-time completion order for put/take; interruption and scheduling also matter. A fair policy generally reduces barging and starvation risk but may reduce throughput. Pay and verify that cost only when the caller contract actually requires waiter ordering.

Follow-up 5: Could this be a lock-free queue?

A lock-free bounded MPMC queue usually needs atomic sequence numbers, CAS, and a much more involved memory-order proof. Its “blocking” behavior still needs a parking and wakeup mechanism; CAS spinning alone is not a blocking queue. The design adds ABA, false sharing, progress guarantees, and platform memory-model concerns. Unless measurements show the single lock is the bottleneck and the team can maintain the proof and stress tests, a standard library class or clear lock-based implementation is safer.

Follow-up 6: Why not use two semaphores directly?

One counting semaphore can represent free slots and another available elements, but updates to the ring's head/tail still need mutual exclusion. Acquiring several synchronization primitives also requires careful exception, interruption, and permit-rollback handling. A semaphore solution can be correct, but it is not automatically shorter than one lock plus two conditions. Either design must prove that permit counts and actual array state never diverge.