Producer-Consumer Queue
Apple● MediumFULLTIMEPHONE SCREENProblem statement
Implement a bounded FIFO producer-consumer queue through this finite operation trace. For this exercise, each submitted call is an atomic step; a blocked call stays pending while later calls may run.
The initially empty queue has capacity slots. PUT submits its corresponding values[i]; it completes when a slot is available. TAKE completes by removing the oldest stored value. A call waits if its required slot or value is unavailable. Pending producers are served in submission order, and pending consumers are served in submission order. After each submission, repeatedly complete every enabled pending call until none is enabled.
Return one final result per submitted call, after the entire trace: PUT for a completed producer, TAKE x for a completed consumer of integer x, or WAIT if still pending. A call that originally blocked may therefore have a completed final result. For TAKE, its input value is zero and is ignored. The queue has no close, cancellation or timeout operation.
Function
runProducerConsumerQueue(capacity: int, operations: String[], values: int[]) → String[]Examples
Example 1
capacity = 1operations = ["PUT","PUT","TAKE"]values = [7,8,0]return = ["PUT","PUT","TAKE 7"]The second producer waits, then completes when the consumer removes7.
Example 2
capacity = 2operations = ["TAKE","TAKE","PUT"]values = [0,0,5]return = ["TAKE 5","WAIT","PUT"]Only the oldest waiting consumer receives the submitted value.
Example 3
capacity = 1operations = ["PUT","PUT"]values = [1,2]return = ["PUT","WAIT"]No later consumer frees the full queue.
Constraints
1 <= capacity <= 1000.0 <= operations.length = values.length <= 2000.- Each operation is
PUTorTAKE. - Producer values are integers in
[-10^9,10^9]; each consumer input value is zero.