FastPrepBounded Producer–Consumer Queue
Problem · Queue

Bounded Producer–Consumer Queue

Learn this problem
● MediumMakeMyTrip.com logoMakeMyTrip.comFULLTIMEONSITE INTERVIEW

Problem statement

Simulate a bounded FIFO task queue from a finite event stream. PRODUCE task enqueues the task and returns ENQUEUED task when capacity is available. If the ready queue is full, the producer joins a FIFO waiting queue and returns WAIT task. CONSUME returns IDLE when no task is ready; otherwise it removes the oldest ready task and returns CONSUMED task. After a successful consume, the oldest waiting producer immediately resumes and its task enters the ready queue; append RESUMED task to that consume result.

Function

simulateBoundedQueue(capacity: int, events: String[]) → String[]

Examples

Example 1

capacity = 2events = ["PRODUCE a","PRODUCE b","PRODUCE c","CONSUME","CONSUME","CONSUME"]return = ["ENQUEUED a","ENQUEUED b","WAIT c","CONSUMED a RESUMED c","CONSUMED b","CONSUMED c"]

c waits until consuming a frees one ready slot.

Example 2

capacity = 1events = ["CONSUME","PRODUCE x","PRODUCE y","CONSUME"]return = ["IDLE","ENQUEUED x","WAIT y","CONSUMED x RESUMED y"]

The first consume is idle; the final consume resumes y.

Constraints

  • 1 <= capacity <= 100000
  • 0 <= events.length <= 200000
  • Each event is exactly PRODUCE task or CONSUME.
  • Task tokens are nonempty ASCII strings without whitespace and are treated as independent tasks.

More MakeMyTrip.com problems

drafts saved locally
public String[] simulateBoundedQueue(int capacity, String[] events) {
    // Write your code here.
}
capacity2
events["PRODUCE a","PRODUCE b","PRODUCE c","CONSUME","CONSUME","CONSUME"]
expected["ENQUEUED a", "ENQUEUED b", "WAIT c", "CONSUMED a RESUMED c", "CONSUMED b", "CONSUMED c"]
checking account