CodingGyan

Producer and Consumer with a Bounded Queue

hard Multithreading and Concurrency

Problem

One producer thread puts the given numbers into a queue that holds at most 3 items, and one consumer thread takes them out. When the queue is full the producer must wait, and when it is empty the consumer must wait. After the last number the producer sends a stop signal. The consumer counts the numbers, adds them up and finds the biggest one. Print three lines: consumed N, sum S and max M.

Constraints

  • 1 <= n <= 10^5
  • |value| <= 10^6

Examples

Input

3
4 9 2

Output

consumed 3
sum 15
max 9

Solutions

Best approachTime O(n)Space O(1)

The bounded queue gives back-pressure: a fast producer cannot fill up memory, because it must wait for the consumer. The stop signal (a poison pill) is a simple way to tell the consumer that no more items come. The JavaScript version only shows the same result, because JavaScript has one thread for your code.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Consumer totals.
 * Input   : n, then n integers.
 * Output  : Three lines.
 * Approach: Bounded queue.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(int[] a) {
        // Step 1: ArrayBlockingQueue has a fixed size. put() waits when it is full and take() waits when it is empty.
        java.util.concurrent.BlockingQueue<Integer> queue = new java.util.concurrent.ArrayBlockingQueue<>(3);
        final int stop = Integer.MIN_VALUE;
        long[] result = new long[3];
        result[2] = Long.MIN_VALUE;

        // Step 2: The producer puts every number, then the stop signal.
        Thread producer = new Thread(() -> {
            try {
                for (int value : a) {
                    queue.put(value);
                }
                queue.put(stop);
            } catch (InterruptedException error) {
                Thread.currentThread().interrupt();
            }
        });

        // Step 3: The consumer takes numbers until it sees the stop signal.
        Thread consumer = new Thread(() -> {
            try {
                while (true) {
                    int value = queue.take();
                    if (value == stop) {
                        break;
                    }
                    result[0]++;
                    result[1] += value;
                    result[2] = Math.max(result[2], value);
                }
            } catch (InterruptedException error) {
                Thread.currentThread().interrupt();
            }
        });
        producer.start();
        consumer.start();
        // Step 4: Wait for both threads. Then the result array is safe to read.
        try {
            producer.join();
            consumer.join();
        } catch (InterruptedException error) {
            throw new IllegalStateException(error);
        }
        return new String[] {"consumed " + result[0], "sum " + result[1], "max " + result[2]};
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(String.join("\n", solve(a)));
    }
}
Hints (1)
  1. What happens to the producer when the consumer is slow?

Try these next