Design Bounded Blocking Queue - Solution & Explanation

Q: Is Design Bounded Blocking Queue easy or hard?

The problem is rated Medium because the queue logic itself is simple, but correct thread synchronization requires understanding concurrency primitives. Many candidates struggle with properly blocking and waking threads without race conditions.

Q: Design Bounded Blocking Queue Python/Java solution

In Python, the queue is typically protected using threading.Lock with threading.Condition objects. In Java, the implementation uses synchronized blocks or ReentrantLock with Condition variables. Both approaches ensure producers block when full and consumers block when empty.

Q: How to solve Design Bounded Blocking Queue in O(1)?

Use a shared queue protected by a mutex and coordinate threads using condition variables or semaphores. Producers block when the queue is full and consumers block when it is empty. Since enqueue and dequeue are constant-time queue operations, the overall complexity remains O(1) per operation.

Q: What is the best approach for Design Bounded Blocking Queue?

The most common solution uses a mutex (or synchronized lock) with condition variables. Producers wait on a "notFull" condition when the queue reaches capacity, and consumers wait on a "notEmpty" condition when the queue is empty. Each operation runs in O(1) time while maintaining thread safety and proper blocking behavior.

Q: Is Design Bounded Blocking Queue asked at Google/Amazon/Meta?

Bounded blocking queue and producer-consumer style problems appear in interviews at companies like Amazon, Google, and Meta when evaluating concurrency knowledge. Interviewers expect candidates to understand synchronization primitives such as locks, condition variables, and semaphores.

Q: What data structure is used in Design Bounded Blocking Queue?

The core structure is a FIFO queue combined with synchronization primitives. A mutex protects the shared queue while condition variables or semaphores control when producer and consumer threads can proceed.

Q: What is the time complexity of Design Bounded Blocking Queue?

Each operation—enqueue, dequeue, and size—runs in O(1) time because they only involve constant-time queue operations and synchronization checks. The space complexity is O(n), where n is the capacity of the bounded queue storing elements.

MediumPremiumFree on FleetCodeConcurrency6 min readAsked at: Microsoft, LinkedIn, Bloomberg

Practice this problem

Problem Statement

Implement a thread-safe bounded blocking queue that has the following methods:

BoundedBlockingQueue(int capacity) The constructor initializes the queue with a maximum capacity.
void enqueue(int element) Adds an element to the front of the queue. If the queue is full, the calling thread is blocked until the queue is no longer full.
int dequeue() Returns the element at the rear of the queue and removes it. If the queue is empty, the calling thread is blocked until the queue is no longer empty.
int size() Returns the number of elements currently in the queue.

Your implementation will be tested using multiple threads at the same time. Each thread will either be a producer thread that only makes calls to the enqueue method or a consumer thread that only makes calls to the dequeue method. The size method will be called after every test case.

Please do not use built-in implementations of bounded blocking queue as this will not be accepted in an interview.

Example 1:

Input:
1
1
["BoundedBlockingQueue","enqueue","dequeue","dequeue","enqueue","enqueue","enqueue","enqueue","dequeue"]
[[2],[1],[],[],[0],[2],[3],[4],[]]

Output:
[1,0,2,2]

Explanation:
Number of producer threads = 1
Number of consumer threads = 1

BoundedBlockingQueue queue = new BoundedBlockingQueue(2);   // initialize the queue with capacity = 2.

queue.enqueue(1);   // The producer thread enqueues 1 to the queue.
queue.dequeue();    // The consumer thread calls dequeue and returns 1 from the queue.
queue.dequeue();    // Since the queue is empty, the consumer thread is blocked.
queue.enqueue(0);   // The producer thread enqueues 0 to the queue. The consumer thread is unblocked and returns 0 from the queue.
queue.enqueue(2);   // The producer thread enqueues 2 to the queue.
queue.enqueue(3);   // The producer thread enqueues 3 to the queue.
queue.enqueue(4);   // The producer thread is blocked because the queue's capacity (2) is reached.
queue.dequeue();    // The consumer thread returns 2 from the queue. The producer thread is unblocked and enqueues 4 to the queue.
queue.size();       // 2 elements remaining in the queue. size() is always called at the end of each test case.

Example 2:

Input:
3
4
["BoundedBlockingQueue","enqueue","enqueue","enqueue","dequeue","dequeue","dequeue","enqueue"]
[[3],[1],[0],[2],[],[],[],[3]]
Output:
[1,0,2,1]

Explanation:
Number of producer threads = 3
Number of consumer threads = 4

BoundedBlockingQueue queue = new BoundedBlockingQueue(3);   // initialize the queue with capacity = 3.

queue.enqueue(1);   // Producer thread P1 enqueues 1 to the queue.
queue.enqueue(0);   // Producer thread P2 enqueues 0 to the queue.
queue.enqueue(2);   // Producer thread P3 enqueues 2 to the queue.
queue.dequeue();    // Consumer thread C1 calls dequeue.
queue.dequeue();    // Consumer thread C2 calls dequeue.
queue.dequeue();    // Consumer thread C3 calls dequeue.
queue.enqueue(3);   // One of the producer threads enqueues 3 to the queue.
queue.size();       // 1 element remaining in the queue.

Since the number of threads for producer/consumer is greater than 1, we do not know how the threads will be scheduled in the operating system, even though the input seems to imply the ordering. Therefore, any of the output [1,0,2] or [1,2,0] or [0,1,2] or [0,2,1] or [2,0,1] or [2,1,0] will be accepted.

Constraints:

1 <= Number of Prdoucers <= 8
1 <= Number of Consumers <= 8
1 <= size <= 30
0 <= element <= 20
The number of calls to enqueue is greater than or equal to the number of calls to dequeue.
At most 40 calls will be made to enque, deque, and size.

Approach Overview

Problem Overview: Design a thread-safe bounded queue with fixed capacity. Multiple producer and consumer threads call enqueue and dequeue. If the queue is full, producers must block until space becomes available. If the queue is empty, consumers must block until an item is inserted.

This problem tests your understanding of concurrency, synchronization primitives, and correct coordination between threads. The core challenge is preventing race conditions while also ensuring threads sleep efficiently instead of spinning.

Approach 1: Busy Waiting with Lock (O(1) time, O(n) space)

A naive solution uses a shared queue protected by a mutex or synchronized block. Each thread repeatedly checks whether the queue has space (for enqueue) or elements (for dequeue). If the condition is not satisfied, the thread keeps looping while holding or repeatedly acquiring the lock. This approach technically works but wastes CPU cycles due to active spinning. In real systems this leads to poor scalability because threads consume CPU while waiting instead of sleeping.

Approach 2: Mutex + Condition Variables (O(1) time, O(n) space)

The standard solution uses a mutex to protect the shared queue and two condition variables: one for not full and one for not empty. When a producer tries to enqueue into a full queue, it waits on the notFull condition. When a consumer removes an element, it signals this condition to wake a producer. Similarly, consumers wait on notEmpty when the queue is empty and get notified after producers insert elements. Each operation locks the mutex, checks the condition in a loop, performs the operation, then signals the appropriate condition. This ensures correct synchronization without wasting CPU cycles.

Approach 3: Semaphore-Based Design (O(1) time, O(n) space)

Another clean design uses semaphores instead of condition variables. Maintain two semaphores: slots (initially equal to capacity) and items (initially 0). Producers acquire slots before inserting and release items afterward. Consumers acquire items before removing and release slots after the removal. A mutex still protects the underlying queue structure. This model maps naturally to producer-consumer problems and is widely used in systems programming and multithreading environments.

Recommended for interviews: The mutex + condition variable approach is what most interviewers expect. It demonstrates that you understand blocking synchronization rather than busy waiting. Semaphore-based implementations are also acceptable and show strong familiarity with concurrency primitives.

Solution

Code

Python Java C++

Python

Java

C++

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Busy Waiting with Lock	O(1)	O(n)	Conceptual understanding of producer-consumer; not ideal for real systems due to CPU waste
Mutex + Condition Variables	O(1)	O(n)	Standard solution for thread-safe blocking queues in interviews and production
Semaphore-Based Design	O(1)	O(n)	Cleaner producer-consumer coordination when semaphore primitives are available

Video Solution

Microsoft Coding Interview Question | Leetcode 1188 | Design Bounded Blocking Queue • WorkWithGoogler • 3,501 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Design Bounded Blocking Queue easy or hard?

The problem is rated Medium because the queue logic itself is simple, but correct thread synchronization requires understanding concurrency primitives. Many candidates struggle with properly blocking and waking threads without race conditions.

Design Bounded Blocking Queue Python/Java solution

In Python, the queue is typically protected using threading.Lock with threading.Condition objects. In Java, the implementation uses synchronized blocks or ReentrantLock with Condition variables. Both approaches ensure producers block when full and consumers block when empty.

How to solve Design Bounded Blocking Queue in O(1)?

Use a shared queue protected by a mutex and coordinate threads using condition variables or semaphores. Producers block when the queue is full and consumers block when it is empty. Since enqueue and dequeue are constant-time queue operations, the overall complexity remains O(1) per operation.

What is the best approach for Design Bounded Blocking Queue?

The most common solution uses a mutex (or synchronized lock) with condition variables. Producers wait on a "notFull" condition when the queue reaches capacity, and consumers wait on a "notEmpty" condition when the queue is empty. Each operation runs in O(1) time while maintaining thread safety and proper blocking behavior.

Is Design Bounded Blocking Queue asked at Google/Amazon/Meta?

Bounded blocking queue and producer-consumer style problems appear in interviews at companies like Amazon, Google, and Meta when evaluating concurrency knowledge. Interviewers expect candidates to understand synchronization primitives such as locks, condition variables, and semaphores.

What data structure is used in Design Bounded Blocking Queue?

The core structure is a FIFO queue combined with synchronization primitives. A mutex protects the shared queue while condition variables or semaphores control when producer and consumer threads can proceed.

What is the time complexity of Design Bounded Blocking Queue?

Each operation—enqueue, dequeue, and size—runs in O(1) time because they only involve constant-time queue operations and synchronization checks. The space complexity is O(n), where n is the capacity of the bounded queue storing elements.

Ready to solve this problem?

Practice Design Bounded Blocking Queue with our built-in code editor and test cases.

Practice on FleetCode

Print in Order

Print FooBar Alternately

Problem Info

DifficultyMedium

Acceptance72.6%

Approaches1

Reading time6 min

Asked at

Microsoft LinkedIn Bloomberg