Design Bounded Blocking Queue
Core idea: A bounded blocking queue is just a FIFO buffer with two "doors" — producers wait at the full door, consumers wait at the empty door — and whoever passes through one door opens the other.
This is one of the most beloved concurrency interview problems because it is small enough to finish in 20 minutes yet deep enough to reveal whether you actually understand Condition variables, semaphores, and the dreaded spurious wakeup. Let's build it from a clumsy first attempt up to a solution so clean it almost looks like cheating.
Problem, rephrased
Imagine a coat check at a theater with exactly capacity hooks.
- A patron (producer) walks up and hands over a coat by calling
enqueue(coat). If every hook is taken, the patron must wait in line at the counter until a hook opens — they do not get to drop the coat on the floor. - An attendant (consumer) calls
dequeue()to grab the next coat to return. If there are no coats waiting, the attendant waits until someone hands one in. size()tells you how many coats are currently on hooks.
Many patrons and many attendants are milling about at once. The coat check must never lose a coat, never exceed its hooks, and — crucially — anyone forced to wait should stand quietly, not pace back and forth checking every millisecond (no busy-spin).
| Operation | When buffer is... | Behavior |
|---|---|---|
enqueue(x) |
has free space | append x to the back, return immediately |
enqueue(x) |
full | block the caller until space frees up, then append |
dequeue() |
has items | remove & return the front (FIFO) |
dequeue() |
empty | block the caller until an item arrives, then remove |
size() |
any | return current count |
The "block" rows are the whole problem. Everything below is about implementing block until a condition becomes true correctly under concurrency.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson