Design Bounded Blocking Queue

Design Bounded Blocking Queue

1. What is this problem about?

The Design Bounded Blocking Queue interview question is a thread-synchronization challenge. You need to implement a queue with a maximum capacity. If a thread tries to add an item to a full queue (enqueue), it must block (wait) until space becomes available. Similarly, if a thread tries to remove an item from an empty queue (dequeue), it must block until an item is added.

2. Why is this asked in interviews?

Companies like Tesla and LinkedIn use the Design Bounded Blocking Queue coding problem to evaluate your knowledge of Concurrency and multi-threading. It tests your ability to use synchronization primitives like Mutexes, Semaphores, or Condition Variables. It's a fundamental test of handling "Race Conditions" and "Deadlocks."

3. Algorithmic pattern used

This problem uses the Producer-Consumer Pattern with Condition Variables.

• Use a standard queue (or a circular array) to store elements.
• Use a Lock/Mutex to ensure atomic access to the queue.
• Use two Condition Variables: notFull and notEmpty.
• enqueue: While queue.size() == capacity, wait on notFull. After adding, signal notEmpty.
• dequeue: While queue.size() == 0, wait on notEmpty. After removing, signal notFull.

4. Example explanation

Capacity = 2.

1. Thread 1 calls enqueue(1). Success.
2. Thread 2 calls enqueue(2). Success.
3. Thread 3 calls enqueue(3). Queue is full. Thread 3 blocks.
4. Thread 4 calls dequeue(). Returns 1. Queue now has space.
5. System signals Thread 3. Thread 3 wakes up and completes enqueue(3).

5. Common mistakes candidates make

• Busy Waiting: Using a while(true) loop without wait() calls, which consumes 100% CPU.
• Using if instead of while: Failing to re-check the condition after being signaled (Spurious Wakeups).
• Signal issues: Forgetting to signal the other condition variable after a successful operation, causing the other threads to block forever.

6. Interview preparation tip

Understand the difference between notify() and notifyAll() (or signal() and broadcast()). In this problem, signal() is usually sufficient because you only need to wake up one waiting producer/consumer, but broadcast() is safer.