Course4all

Design Bounded Blocking Queue

Expert Answer & Key Takeaways

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on State Management and API Design. ### Core Principles 1. Encapsulation: Keep data private and expose functionality through well-defined methods. 2. Trade-offs: Every design choice has a cost. Is it better to have O(1)O(1) read and O(N)O(N) write, or vice versa? 3. State Consistency: Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for O(1)O(1) caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - HashMap: Provides O(1)O(1) lookups for keys to their corresponding nodes. - DLL: Provides O(1)O(1) addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in Queue using Stacks or Dynamic Arrays. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is O(1)O(1), and "flipping" elements to another stack happens only when necessary, averaging O(1)O(1) per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., Circular Queue, Hit Counter). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., Bounded Blocking Queue). - Use Mutexes (Locks) to prevent data races. - Use Condition Variables (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. Identify the API: What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. Define the State: What variables represent the current state? (Size, Capacity, Pointers). 3. Choose the Data Structures: Select the combination that minimizes time complexity for the most frequent operations. 4. Dry Run: Trace the state changes through a sequence of operations based on your chosen structure.

Design Bounded Blocking Queue

Implement a thread-safe bounded blocking queue. Submitting a task to a full queue should block the calling thread until a slot becomes available. Fetching a task from an empty queue should block the calling thread until a task becomes available.
Hard

Examples

Input: BoundedBlockingQueue(2), enqueue(1), enqueue(2), dequeue() (blocks if empty)
Output: 1
Approach 1

Level I: Synchronized Methods with wait/notify

Intuition

Use synchronized on enqueue and dequeue. Inside each, use a while loop to wait() if the condition (full or empty) isn't met, and notifyAll() after making a change. This is the classic Java threading building block.
⏱ O(1) excluding wait time.💾 O(Capacity).

Detailed Dry Run

Thread 1: Enqueue(1). Thread 2: Enqueue(2). Thread 3: Enqueue(3) -> waits (full). Thread 4: Dequeue() -> returns 1, signals threads.
java
class BoundedBlockingQueue {
    private Queue<Integer> q = new LinkedList<>();
    private int cap;
    public BoundedBlockingQueue(int capacity) { cap = capacity; }
    public synchronized void enqueue(int e) throws InterruptedException {
        while(q.size() == cap) wait();
        q.add(e); notifyAll();
    }
    public synchronized int dequeue() throws InterruptedException {
        while(q.isEmpty()) wait();
        int res = q.poll(); notifyAll(); return res;
    }
}
Approach 2

Level II: Semaphores

Intuition

Use Semaphore fill = new Semaphore(0) and Semaphore drain = new Semaphore(cap). enqueue calls drain.acquire() and fill.release(). dequeue does the reverse.
⏱ O(1) excluding wait time.💾 O(Capacity).
java
class BoundedBlockingQueue {
    Semaphore fill, drain; Queue<Integer> q = new LinkedList<>();
    public BoundedBlockingQueue(int cap) {
        fill = new Semaphore(0); drain = new Semaphore(cap);
    }
    public void enqueue(int el) throws InterruptedException {
        drain.acquire(); synchronized(q) { q.add(el); } fill.release();
    }
    public int dequeue() throws InterruptedException {
        fill.acquire(); int res; synchronized(q) { res = q.poll(); } drain.release();
        return res;
    }
}
Approach 3

Level III: Condition Variables (Producer-Consumer)

Intuition

Use a ReentrantLock with two Condition variables (e.g., notEmpty, notFull). Threads wait on these conditions when the queue is empty or at capacity, and signal each other when appropriate.
⏱ O(1) excluding wait time.💾 O(Capacity).
java
class BoundedBlockingQueue {
    private final Lock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();
    private final Queue<Integer> queue = new LinkedList<>();
    private final int capacity;
    public BoundedBlockingQueue(int capacity) { this.capacity = capacity; }
    public void enqueue(int element) throws InterruptedException {
        lock.lock();
        try {
            while (queue.size() == capacity) notFull.await();
            queue.add(element); notEmpty.signal();
        } finally { lock.unlock(); }
    }
    public int dequeue() throws InterruptedException {
        lock.lock();
        try {
            while (queue.isEmpty()) notEmpty.await();
            int element = queue.poll(); notFull.signal(); return element;
        } finally { lock.unlock(); }
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionSnapshot Array
Next Question →Design In-Memory File System