FastPrepImplement a Multithreaded Bounded Queue
Problems/Implement a Multithreaded Bounded Queue

Implement a Multithreaded Bounded Queue

AMD logoAMD● MediumFULLTIMEONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report says the third technical round asked for a multithreaded queue after C++ smart pointers and a stack. It gives no queue API, capacity, worker count, scheduling rule or tests. This exercise authors a bounded two-producer/two-consumer interface, item tags, deterministic per-producer audit and empty/full/finish rules. References use actual synchronized workers; the output audit is not a proof over all schedules. Approximate source match: 70%. An exact source date is not available.

Implement a bounded FIFO queue and use it with two producer workers and two consumer workers. Producer p sends its input row from left to right. Tag every item with its producer ID, its zero-based position in that row, and its value. The queue starts empty, holds at most capacity items, blocks a producer while full, and blocks a consumer while empty if a producer can still send an item. Stop consumers only when both producers have finished and the queue is empty.

Start all four workers behind a common start gate. Use real threads: Python threads, Java threads, C++ threads, Go workers each locked to an OS thread, or JavaScript Node Worker threads. Use synchronization for shared state. Do not replace workers with a serial loop or promises, and do not use a library blocking-queue implementation. A condition wait must recheck its predicate. Do not use fixed sleeps to make a schedule appear correct.

Both consumers update the following audit in the same critical section that removes an item. For each producer, start with count = 0 and hash = 0. If an item's position differs from that producer's current count, add 1 to violations. Then increase count by 1 and set hash = (hash * 31 + value + 1000) % 1000003. Return [[count0,hash0],[count1,hash1],[remaining,violations]] after every worker has finished. A correct run consumes every item exactly once, preserves each producer's order and global queue FIFO order, and returns remaining = 0 and violations = 0. Interleaving between producers and which consumer receives an item are unrestricted.

The numeric judge compares this finite audit; it does not prove the absence of every possible concurrency bug or verify thread usage by output alone. The implementation requirements still apply. References use a mutex and condition waiting, or the corresponding shared-memory atomic lock and change notification in Node.

Function

auditQueue(producers: int[][], capacity: int) → int[][]

Examples

Example 1

producers = [[1,2],[7]]capacity = 1return = [[2,32033],[1,1007],[0,0]]

Consumers receive producer 0’s values 1 then 2: its hash becomes 1001, then 1001 * 31 + 1002 = 32033. Producer 1’s value 7 gives hash 1007. Their counts are 2 and 1; the queue ends empty with no order violations.

Example 2

producers = [[-1000],[1000,0]]capacity = 2return = [[1,0],[2,63000],[0,0]]

Producer 0 sends -1000, which contributes 0 to its hash. Producer 1 sends 1000 then 0, giving hashes 2000 then 63000. The counts are 1 and 2; all items are consumed with no order violations.

Constraints

  • The producers array contains exactly two rows.
  • 0 <= producers[p].length <= 16 for p in 0..1.
  • -1000 <= producers[p][i] <= 1000.
  • 1 <= capacity <= 8.

More AMD problems

  • Insert After a Linked-List NodeONSITE INTERVIEW · Seen Oct 2026
  • LRU CacheONSITE INTERVIEW · Seen Oct 2026
  • Lowest Common Ancestor of a Binary TreePHONE SCREEN · Seen Oct 2026
All AMD interview questionsSee AMD hiring insights
Saved
public int[][] auditQueue(int[][] producers, int capacity) {
    // Write your code here.
}
Checking account…