Leetcode #1188: Design Bounded Blocking Queue
In this guide, we solve Leetcode #1188 Design Bounded Blocking Queue in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
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.
Quick Facts
- Difficulty: Medium
- Premium: Yes
- Tags: Concurrency
Intuition
The constraints allow a direct scan that keeps only the essential state.
By translating the requirements into a clean loop, the logic stays easy to reason about.
Approach
Iterate through the data once, updating the state needed to compute the answer.
Return the final state after the traversal is complete.
Steps:
- Parse the input.
- Iterate and update state.
- Return the computed answer.
Example
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.
Python Solution
from threading import Semaphore
class BoundedBlockingQueue(object):
def __init__(self, capacity: int):
self.s1 = Semaphore(capacity)
self.s2 = Semaphore(0)
self.q = deque()
def enqueue(self, element: int) -> None:
self.s1.acquire()
self.q.append(element)
self.s2.release()
def dequeue(self) -> int:
self.s2.acquire()
ans = self.q.popleft()
self.s1.release()
return ans
def size(self) -> int:
return len(self.q)
Complexity
The time complexity is O(n). The space complexity is O(1) to O(n).
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.