Implement a Multithreaded Bounded Queue
Problem statement
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 <= 16for p in 0..1.-1000 <= producers[p][i] <= 1000.1 <= capacity <= 8.