How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Anthropic.

What role is this question designed for?

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

Implement thread-safe blocking queue | Anthropic Coding Question

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)

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).

Quick Overview

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