Design Thread-Safe Blocking Queue — Low-level design | OneNoughtOne

0/105

00:00:00

Design Thread-Safe Blocking Queue

Intermediate

Design a thread-safe blocking queue implementing the classic producer-consumer pattern. The queue provides blocking operations (put blocks when full, take blocks when empty) and timed operations (offer/poll with timeout). Implement three variants: (1) ArrayBlockingQueue — bounded circular buffer with a single lock and two Conditions (notFull for producers, notEmpty for consumers), using while-loops to guard against spurious wake-ups; (2) LinkedBlockingQueue — optionally bounded linked list with TWO separate locks (putLock + takeLock) allowing concurrent put and take, with AtomicInteger count for cross-lock coordination; (3) PriorityBlockingQueue — unbounded min-heap where take blocks when empty but put never blocks, dequeuing items in priority order. All variants enforce non-null items and provide peek, size, isEmpty, and bulk drain operations.

Core Use Cases

put() — blocking insert

Block the producer thread until space is available, then insert at tail of the circular buffer

take() — blocking remove

Block the consumer thread until an item is available, then remove and return from head

offer() — timed insert

Try to insert with an optional timeout; return false if queue remains full after timeout

poll() — timed remove

Try to remove with an optional timeout; return null if queue remains empty after timeout

Circular array buffer

Fixed-size array with head and tail indices wrapping via modulo; O(1) enqueue and dequeue

Two-Condition signalling

notFull Condition wakes producers; notEmpty Condition wakes consumers — avoids unnecessary wake-ups vs single Condition

Two-lock linked variant

LinkedBlockingQueue with separate putLock and takeLock allows concurrent put+take; AtomicInteger count coordinates

Priority blocking queue

Unbounded queue backed by a min-heap; take blocks when empty, put never blocks; items dequeued in priority order

Bulk operations

drain_to() transfers multiple items atomically; clear() removes all and wakes waiting producers

Constraints

ArrayBlockingQueue has a fixed capacity set at construction time
put() blocks indefinitely if queue is full (until space freed by take/poll)
take() blocks indefinitely if queue is empty (until item added by put/offer)
Null items are not permitted (null is used as sentinel for 'no item')
offer/poll with timeout return false/null when deadline expires
LinkedBlockingQueue uses two separate locks — putLock and takeLock — for higher throughput
PriorityBlockingQueue is unbounded; put never blocks, only take blocks when empty

Assumptions

Standard threading primitives available (Lock, Condition, mutex, condition_variable)
No distributed queue semantics (single process only)
Items are not persisted (in-memory only)
Fair vs unfair locking is not required (FIFO wake-up not guaranteed)
TypeScript uses async/await with Promises to simulate blocking (single-threaded model)

In Scope

ArrayBlockingQueue: bounded, circular buffer, single lock, two Conditions
LinkedBlockingQueue: optionally bounded, linked list, two-lock design
PriorityBlockingQueue: unbounded, min-heap, single lock
Blocking operations: put(), take()
Timed operations: offer(timeout), poll(timeout)
Non-blocking: peek(), size(), isEmpty(), isFull(), remainingCapacity()
Bulk: drainTo(), clear()
Producer-consumer demo with threads

Out of Scope

Distributed message queue (Kafka, RabbitMQ)
Persistence / durability
Fair locking (strict FIFO ordering of waiting threads)
Transfer queue (SynchronousQueue-style direct handoff)
Delay queue (items available only after a delay)
Work-stealing deque

Approach Guide(Click to expand each section)

Before diving into code, clarify the use cases and edge cases. Understanding the problem deeply leads to better class design.

List Core Use Cases

Identify the primary actions users will perform. For a parking lot: park vehicle, exit vehicle, check availability. Each becomes a method.

Identify Actors

Who interacts with the system? Customers, admins, automated systems? Each actor type may need different interfaces.

Clarify Constraints

What are the limits? Max vehicles, supported vehicle types, payment methods. Constraints drive your data structures.

Ask About Edge Cases

What happens on overflow? Concurrent access? Payment failures? Thinking about edge cases reveals hidden complexity.

Follow-up Questions(Questions an interviewer might ask)

💡 Draw UML class diagrams, sequence diagrams, or any design visualizations. Submit from the Code tab.

Loading canvas...

00:00:00

Design Thread-Safe Blocking Queue

Intermediate

Design a thread-safe blocking queue implementing the classic producer-consumer pattern. The queue provides blocking operations (put blocks when full, take blocks when empty) and timed operations (offer/poll with timeout). Implement three variants: (1) ArrayBlockingQueue — bounded circular buffer with a single lock and two Conditions (notFull for producers, notEmpty for consumers), using while-loops to guard against spurious wake-ups; (2) LinkedBlockingQueue — optionally bounded linked list with TWO separate locks (putLock + takeLock) allowing concurrent put and take, with AtomicInteger count for cross-lock coordination; (3) PriorityBlockingQueue — unbounded min-heap where take blocks when empty but put never blocks, dequeuing items in priority order. All variants enforce non-null items and provide peek, size, isEmpty, and bulk drain operations.

Core Use Cases

put() — blocking insert

Block the producer thread until space is available, then insert at tail of the circular buffer

take() — blocking remove

Block the consumer thread until an item is available, then remove and return from head

offer() — timed insert

Try to insert with an optional timeout; return false if queue remains full after timeout

poll() — timed remove

Try to remove with an optional timeout; return null if queue remains empty after timeout

Circular array buffer

Fixed-size array with head and tail indices wrapping via modulo; O(1) enqueue and dequeue

Two-Condition signalling

notFull Condition wakes producers; notEmpty Condition wakes consumers — avoids unnecessary wake-ups vs single Condition

Two-lock linked variant

LinkedBlockingQueue with separate putLock and takeLock allows concurrent put+take; AtomicInteger count coordinates

Priority blocking queue

Unbounded queue backed by a min-heap; take blocks when empty, put never blocks; items dequeued in priority order

Bulk operations

drain_to() transfers multiple items atomically; clear() removes all and wakes waiting producers

Constraints

ArrayBlockingQueue has a fixed capacity set at construction time
put() blocks indefinitely if queue is full (until space freed by take/poll)
take() blocks indefinitely if queue is empty (until item added by put/offer)
Null items are not permitted (null is used as sentinel for 'no item')
offer/poll with timeout return false/null when deadline expires
LinkedBlockingQueue uses two separate locks — putLock and takeLock — for higher throughput
PriorityBlockingQueue is unbounded; put never blocks, only take blocks when empty

Assumptions

Standard threading primitives available (Lock, Condition, mutex, condition_variable)
No distributed queue semantics (single process only)
Items are not persisted (in-memory only)
Fair vs unfair locking is not required (FIFO wake-up not guaranteed)
TypeScript uses async/await with Promises to simulate blocking (single-threaded model)

In Scope

ArrayBlockingQueue: bounded, circular buffer, single lock, two Conditions
LinkedBlockingQueue: optionally bounded, linked list, two-lock design
PriorityBlockingQueue: unbounded, min-heap, single lock
Blocking operations: put(), take()
Timed operations: offer(timeout), poll(timeout)
Non-blocking: peek(), size(), isEmpty(), isFull(), remainingCapacity()
Bulk: drainTo(), clear()
Producer-consumer demo with threads

Out of Scope

Distributed message queue (Kafka, RabbitMQ)
Persistence / durability
Fair locking (strict FIFO ordering of waiting threads)
Transfer queue (SynchronousQueue-style direct handoff)
Delay queue (items available only after a delay)
Work-stealing deque

Approach Guide(Click to expand each section)

Before diving into code, clarify the use cases and edge cases. Understanding the problem deeply leads to better class design.

List Core Use Cases

Identify the primary actions users will perform. For a parking lot: park vehicle, exit vehicle, check availability. Each becomes a method.

Identify Actors

Who interacts with the system? Customers, admins, automated systems? Each actor type may need different interfaces.

Clarify Constraints

What are the limits? Max vehicles, supported vehicle types, payment methods. Constraints drive your data structures.

Ask About Edge Cases

What happens on overflow? Concurrent access? Payment failures? Thinking about edge cases reveals hidden complexity.

Follow-up Questions(Questions an interviewer might ask)

💡 Draw UML class diagrams, sequence diagrams, or any design visualizations. Submit from the Code tab.

Loading canvas...

Design Thread-Safe Blocking Queue

Core Use Cases

Constraints

Assumptions

In Scope

Out of Scope

Approach Guide(Click to expand each section)

Follow-up Questions(Questions an interviewer might ask)

Explore the full editorial.

Sign in to view submissions

Design Thread-Safe Blocking Queue

Core Use Cases

Constraints

Assumptions

In Scope

Out of Scope

Approach Guide(Click to expand each section)

Follow-up Questions(Questions an interviewer might ask)

Explore the full editorial.

Sign in to view submissions

Design Thread-Safe Blocking Queue

Core Use Cases

Constraints

Assumptions

In Scope

Out of Scope

Approach Guide(Click to expand each section)

Gather Requirements~3 min

Identify Classes & Entities~4 min

Define Relationships~3 min

Apply Design Patterns~4 min

Apply SOLID Principles~3 min

Code Organization~2 min

Follow-up Questions(Questions an interviewer might ask)

1Why does LinkedBlockingQueue use two locks instead of one? What's the throughput benefit?

2How would you implement a SynchronousQueue (zero-capacity direct handoff)?

3How would you add fairness to the blocking queue?

4How would you implement a DelayQueue where items are only available after their delay expires?

5How would you handle poison pills for graceful shutdown of producer-consumer pipelines?

Key Topics

Asked At

Explore the full editorial.

Sign in to view submissions

Design Thread-Safe Blocking Queue

Core Use Cases

Constraints

Assumptions

In Scope

Out of Scope

Approach Guide(Click to expand each section)

Gather Requirements~3 min

Identify Classes & Entities~4 min

Define Relationships~3 min

Apply Design Patterns~4 min

Apply SOLID Principles~3 min

Code Organization~2 min

Follow-up Questions(Questions an interviewer might ask)

1Why does LinkedBlockingQueue use two locks instead of one? What's the throughput benefit?

2How would you implement a SynchronousQueue (zero-capacity direct handoff)?

3How would you add fairness to the blocking queue?

4How would you implement a DelayQueue where items are only available after their delay expires?

5How would you handle poison pills for graceful shutdown of producer-consumer pipelines?

Key Topics

Asked At

Explore the full editorial.

Sign in to view submissions