Implement thread-safe blocking queue
Company: Anthropic
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
Design and implement a thread-safe bounded blocking queue that supports concurrent enqueue and dequeue operations using standard synchronization primitives (e.g., mutexes, condition variables). Discuss time-complexity and potential deadlock issues.
Quick Answer: This question evaluates competency in concurrent programming, synchronization primitives, and implementation of thread-safe bounded blocking queues within the Coding & Algorithms domain.
You are given a queue capacity and a non-decreasing time-ordered list of operations to a bounded blocking queue. Each operation is a string: either "ENQ t v" (enqueue value v at time t) or "DEQ t" (dequeue at time t). Simulate the queue with FIFO fairness and blocking semantics:
- ENQ at time t: if any DEQ is waiting, immediately pair with the oldest waiting DEQ; both complete at time t and the item is not stored in the buffer. Otherwise, if the buffer has space, insert the value and the ENQ completes at time t; else the ENQ waits.
- DEQ at time t: if the buffer has an item, remove the oldest and the DEQ completes at time t. After removing, if any ENQ is waiting and there is space, exactly one waiting ENQ inserts and completes at time t. If the buffer is empty but an ENQ is waiting (only possible when capacity is 0), immediately pair with the oldest waiting ENQ; both complete at time t. Otherwise, the DEQ waits.
Process operations in input order for equal times. Return one string per input operation in the same order: for ENQ, "OK <completion_time>"; for DEQ, "<value> <completion_time>". It is guaranteed that no operation remains blocked after processing the list.
Constraints
- 0 <= capacity <= 100000
- 1 <= len(ops) <= 200000
- Each op is exactly "ENQ t v" or "DEQ t"
- 0 <= t <= 1e9
- -1e9 <= v <= 1e9
- Operation times are non-decreasing; input order breaks ties at equal times
- All operations complete by the end (no thread remains blocked)
Solution
from collections import deque
def simulate_blocking_queue(capacity: int, ops: list[str]) -> list[str]:
n = len(ops)
res: list[str | None] = [None] * n
buffer = deque() # stores values currently in the queue
waiting_enq = deque() # stores tuples (idx, t, v) for blocked ENQ
waiting_deq = deque() # stores tuples (idx, t) for blocked DEQ
for idx, op in enumerate(ops):
parts = op.strip().split()
if not parts:
continue
if parts[0] == "ENQ":
t = int(parts[1])
v = int(parts[2])
# If any DEQ is waiting, pair immediately (handshake, no buffer change)
if waiting_deq:
deq_idx, _ = waiting_deq.popleft()
res[deq_idx] = f"{v} {t}"
res[idx] = f"OK {t}"
else:
# Try to insert into buffer; otherwise, wait
if len(buffer) < capacity:
buffer.append(v)
res[idx] = f"OK {t}"
else:
waiting_enq.append((idx, t, v))
else: # DEQ
t = int(parts[1])
if buffer:
# Consume from buffer
v = buffer.popleft()
res[idx] = f"{v} {t}"
# After removing, if an ENQ is waiting and there is space, wake exactly one
if waiting_enq and len(buffer) < capacity:
enq_idx, enq_t, enq_v = waiting_enq.popleft()
buffer.append(enq_v)
res[enq_idx] = f"OK {t}"
else:
# Buffer empty: if any ENQ waits (only possible when capacity == 0), pair immediately
if waiting_enq:
enq_idx, enq_t, enq_v = waiting_enq.popleft()
res[enq_idx] = f"OK {t}"
res[idx] = f"{enq_v} {t}"
else:
waiting_deq.append((idx, t))
# Per constraints, all operations must be completed by now
return res # type: ignore[return-value]
Explanation
Use three FIFO queues: (1) the actual buffer for stored items, (2) a queue of blocked enqueues (index, time, value), and (3) a queue of blocked dequeues (index, time). For each ENQ, first serve a waiting DEQ if any (direct handoff), otherwise insert into the buffer if space exists, otherwise block the ENQ. For each DEQ, if the buffer has items, pop one and complete; after popping, if an ENQ is waiting and there is space, wake exactly one ENQ to fill the freed slot at the same time. If the buffer is empty but there is a waiting ENQ (capacity zero case), immediately pair them. Maintain FIFO order among waiting operations and process input in stable order for identical timestamps. This directly simulates a bounded blocking queue's behavior without threads.
Time complexity: O(n). Space complexity: O(n).
Hints
- Maintain three FIFO queues: the buffer, waiting enqueues, and waiting dequeues.
- On ENQ: first try to match a waiting DEQ; otherwise push to buffer if space, else enqueue to waiting ENQ queue.
- On DEQ: pop from buffer if available; after popping, wake exactly one waiting ENQ if space exists. If buffer empty and a waiting ENQ exists (capacity 0), pair with it immediately.
- Preserve input order for operations at the same time and for serving waiters (FIFO).