445. Ring Buffer

MediumQueueDesignArray3 hints
RPby Rohit Parihar

A sensor logger owns a fixed block of memory with room for exactly k readings and must reuse the freed slots once old readings are consumed. Readings are consumed in the order they were stored, and nothing may be shifted around in memory when that happens.

Implement RingBuffer, a bounded circular queue. The constructor takes the capacity k. enQueue(value) appends a value at the back and returns true, or returns false if the buffer is full. deQueue() removes the front value and returns true, or returns false if the buffer is empty. front() and rear() return the first and the last stored value, or -1 when the buffer is empty. isEmpty() and isFull() return booleans. All values are non-negative, so -1 is never a stored value.

Example 1

Input:
operations = ["RingBuffer","enQueue","enQueue","enQueue","enQueue","rear","deQueue","enQueue","front","rear","isFull"]arguments = [[3],[18],[27],[36],[45],[],[],[45],[],[],[]]
Output:
[null,true,true,true,false,36,true,true,27,45,true]
Explanation:

The buffer accepts 18, 27, 36 and rejects 45 (false) because capacity is 3; rear is 36. After one deQueue the freed slot accepts 45, so front is 27, rear is 45 and the buffer is full.

Example 2

Input:
operations = ["RingBuffer","front","isEmpty","enQueue","deQueue","deQueue","rear"]arguments = [[2],[],[],[9],[],[],[]]
Output:
[null,-1,true,true,true,false,-1]
Explanation:

On an empty buffer front is -1 and isEmpty is true. After storing 9 and removing it, a second deQueue fails (false) and rear is -1 again.

Constraints

1 ≤ k ≤ 1000
0 ≤ value ≤ 1000
At most 3000 calls in total.

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(1) per operation
Space
O(k)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.