hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Design Bounded Blocking Queue
Problem: 1188. Design Bounded Blocking Queue
Problem Link:
Companies Asked: LinkedIn, Rubrik, Apple, Bloomberg, Microsoft, Adobe, eBay, Uber, Nvidia
Approach:
First off, initiate a queue (https://cplusplus.com/reference/queue/queue/) to store the encountered element say the main queue.
And another queue for storing elements that will not be inserted into the main queue say, another queue.
When there is an enqueue() call will check if the main queue is filled or not.
If not then insert the element into the main queue. Otherwise, insert the element into another queue.
Now when there is a deque() call, remove an element from main_queue. Now there are two situations -
If there are some elements in another queue then, put the front element into main_queue and remove it from the another_queue.
If there is no such elements in the main_queue as well, keep this deque call on track. When there is an enqueue call, first enqueue the element and then deque it.
Return the dequeued element.
When the size() is called return the main_queue size.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(N)
Code [C++]
#include <bits/stdc++.h>
class BoundedBlockingQueue
{
public:
queue<int>Q, temp_Q;
int Cap, del_Q;
BoundedBlockingQueue(int Capacity)
{
Cap = Capacity; del_Q = 0;
}
void Enqueue(int val)
{
if(Q.size() < Cap){
Q.push(val);
while(del_Q > 0 && Q.size() > 0){
del_Q--;
cout<<Dequeue()<<" ";
}
}
else{
temp_Q.push(val);
}
}
int Dequeue()
{
int ret = -1;
if(Q.size() > 0){
ret = Q.front();
Q.pop();
if(!temp_Q.empty()){
Q.push(temp_Q.front());
temp_Q.pop();
}
}
else{
del_Q++;
}
return ret;
}
int size()
{
return Q.size();
}
};