Quick Overview

This question evaluates competency in concurrent programming, synchronization primitives, and implementation of thread-safe bounded blocking queues within the Coding & Algorithms domain.

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.

Overview: 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)

Hints

  1. Maintain three FIFO queues: the buffer, waiting enqueues, and waiting dequeues.
  2. On ENQ: first try to match a waiting DEQ; otherwise push to buffer if space, else enqueue to waiting ENQ queue.
  3. 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.
  4. Preserve input order for operations at the same time and for serving waiters (FIFO).

Loading coding console...

Show the approach

Approach

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)