Design and implement a thread-safe bounded queue supporting multiple producers and consumers. Provide blocking enqueue/dequeue with timeouts, avoid deadlocks and starvation, and ensure fairness under contention. Discuss your locking strategy (mutexes vs. lock-free), condition/signaling mechanisms, backpressure handling when the queue is full, and how you'd test correctness and performance. Analyze time and space complexity.

This question evaluates skills in concurrent programming, synchronization primitives, and designing thread-safe bounded data structures that support blocking operations with timeouts, fairness, and backpressure.

How do I approach System Design interview questions?

System Design questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master system design interviews.

What difficulty level is this interview question?

This is a hard difficulty System Design question, commonly asked during HR Screen rounds at Databricks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Databricks during technical interviews.

Design a thread-safe bounded queue | Databricks Interview Question

Design a Thread-Safe Bounded MPMC Queue with Timeouts and Fairness

Context

You are building a reusable, in-memory, bounded queue that supports multiple producers and multiple consumers (MPMC). Operations must block with timeouts, avoid deadlocks and starvation, and be fair under contention.

Requirements

Provide a bounded queue with capacity N.
Support blocking operations with timeouts:
1. enqueue(item, deadline) → true on success; false on timeout.
2. dequeue(deadline) → item on success; timeout error/null on timeout.
Ensure:
- Thread safety with many producers and consumers.
- No deadlocks.
- No starvation; enforce fairness under contention.
- Backpressure when the queue is full.
Discuss:
- Locking strategy (mutexes vs. lock-free).
- Condition/signaling mechanisms.
- Backpressure policy.
- Testing strategy for correctness and performance.
- Time and space complexity.

Assumptions

Language/runtime provides mutexes, condition variables, and monotonic clocks for timeouts.
Capacity N ≥ 1; item copy/move is safe and does not invoke user code while locks are held.
If needed, define a close()/shutdown() method to wake waiters and terminate gracefully.

Requirements

Provide a bounded queue with capacity N.

Support blocking operations with timeouts:

enqueue(item, deadline) → true on success; false on timeout.
dequeue(deadline) → item on success; timeout error/null on timeout.

Ensure:

Thread safety with many producers and consumers.
No deadlocks.
No starvation; enforce fairness under contention.
Backpressure when the queue is full.

Discuss:

Locking strategy (mutexes vs. lock-free).
Condition/signaling mechanisms.
Backpressure policy.
Testing strategy for correctness and performance.
Time and space complexity.

Design a thread-safe bounded queue

Quick Overview

Design a Thread-Safe Bounded MPMC Queue with Timeouts and Fairness

Context

Requirements

Assumptions

Solution

Comments (0)

Design a thread-safe bounded queue

Quick Overview

Design a Thread-Safe Bounded MPMC Queue with Timeouts and Fairness

Context

Requirements

Assumptions

Solution

Comments (0)