Question – 3 & 4 (Circular queue and LL ), 5 & 6 (Stack and Queue implementation), 10 (LRU Cache),
Queue<Integer> q = new LinkedList<>();
- ** Basic Queue Video
A queue is First In First Out (FIFO) DS. It has 4 basic method in it’s implementation –
enqueue(), dequeue(), isEmpty(), front()
There are two popular implementation of queue – using array and using linked list. The problem with array implementation is wastage of space. As the rear and front moves towards the end, the starting of the array although vacant can’t be utilized.
Since the queue is only the part between front and rear. To overcome this problem we use circular array for implementing queue.
- *** Java Queue methods
The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or “bounded”) queues.
The remove() and poll() methods remove and return the head of the queue. Exactly which element is removed from the queue is a function of the queue’s ordering policy, which differs from implementation to implementation. The remove() and poll() methods differ only in their behavior when the queue is empty: the remove() method throws an exception, while the poll() method returns null. NoSuchElementException is thrown by remove() if we try to remove element from an empty queue.
The element() and peek() methods return, but do not remove, the head of the queue.
isEmpty() to check if queue is empty. It returns boolean.Java provides us
Queueinterface, where we can keep and handle elements before processing. Except the methods that
Collectionprovides, it also supports some basic operations in order to simulate the classic queue structure. Each of these operations exists in two forms:
- if a method fails, an exception is thrown. This form includes
- if a method fails, a special value is returned (null or false). This form contains
How to use Queue with Linked List – Basic Java Queue Collection
Queue<Integer> q =
- if a method fails, an exception is thrown. This form includes
- *** Circular Queue implementation using Array Code
You should know what’s the problem with non-circular array implementation of queue using Array. Just need to use the modulo properly. We can have a separate variable that keeps track of the current size. This helps in simple implementation of isEmpty() and isFull(). In the current implementation, while enqueue(), we first change the rear index and then insert the value and while dequeue() we first dequeue the element and then change the front index. Why ?
Try to set the front and rear with index = 0. You will face the issue of rollover for insert from the last index. So for rollover we start front from the last index of the queue capacity given.
Increment and insert. Remove and increment.
- *** Queue using Linked List – Code
Algo: We basically need to create a queue using Node like we do in linked list.
We will have a front and rear pointer. We don’t need capacity here as there’s no size issue(pre-allocation issue). When we add a new node to queue we check if the queue is empty, if yes we change both front and rear. If it’s not empty we only change the rear. Similarly while deQueue() we check if the queue is empty. If not we change the front. We need to handle the case when we the dequeue() operation will make the queue empty, in this case the rear will also be updated to null.
- *** Code – Implement Queue using Stacks
Algo: (using 2 stack) We create two stack, s1 and s2. s1 is the one where all queue operation happen. When we need to dequeue, we move all s1 item to s2 and pop from s2, until s2 is empty. This will have a FIFO effect. Now we keep popping from s2(for every dequeue op) until it’s empty and meanwhile all push op will be in s1. When s2 is empty and another dequeue op is needed we pop all s1 to s2.
- *** Implement Stack using Queue –
Using One Queue – In a queue, elements are added to the end and removed from the front. For the current implementation when we add the element will be added to the front of queue, so we remove everything from the front and add it again(which will automatically be added to the end of queue, effectively reversing the queue).
We do this for every element that’s added to the queue. So the pop operation will pop the last element added, LIFO like a stack.
Using Two Queue – Idea is to push elements into the Queue “mainQueue” and while popping element, pop all elements except the last element one by one from “mainQueue” to temporary Queue “tempQueue”, return the last element and initialize “mainQueue” with “tempQueue”.
One small but impactful change we do is, while copying tempQueue to mainQueue, we do not actually copy the data but initialize mainQueue = tempQueue and reinitialize the tempQueue. Basically renaming temp to main and creating a new temp.
mainQueue = tempQueue;
tempQueue = new LinkedList();
- How to efficiently implement k Queues in a single array? –
1. divide an array and handle it
2. [Skip] like efficiently implement k Stack in a single array? – this will be like the dynamic solution we saw in byte-by-byte.
- Implement two queue in a single array – Doesn’t seems like a popular interview question as I din’t find it online. But if we had implement it we could just divide an array into two part.
f1 = 0, r1 = -1 , f2 = 3, r2 = 2; => if we had an array of size 6. Now the first queue will work smoothly(implement the circular queue logic). For the second queue we always add the 3 to the index generated before enqueue/dequeue (3 because the second queue starts from index 3 in the array).
- Reverse a queue –
1. Recursion –
– If we implemented a queue ourselves using Linked List then it will be a problem of reversing a linked list.
– In our code we are using Java’s collection to implement Queue using linked List. This is also simple recursion.
2. Using stack – in recursion we use the system stack, instead of that we will have to push to another user defined stack
- **** LRU Cache – This is the most important question on this page.
Algo: Use a HashMap along with DDL. We use a DDL to implement the least recently used eviction policy. The hashmap stores the key and the value corresponding to the key is the node in the DDL. Whenever an element is added or read from the hashmap we need to move it to the head of the DDL. When the max size it reached to we remove the element at the end of the DDL.
- Find the first circular tour that visits all petrol pumps – Code
Algo: We start from the first pump and consider that it should be the first petrol pump to start with. We calculate the diff of the distance and gas(call it delta). If the sum of all delta till now has been positive we add then we add the current delta to it. If the delta till now has become negative we know that our starting point was not correct and consider the current petrol bunk as our starting point and reset this uptonow value. At the same time we keep adding all the delta(called total). If at the end of journey this is negative we take it that the journey is not possible.
- [Pending] Given absolute unix like path simply it – SimplyPath.java
- [Skip] An Interesting Method to Generate Binary Numbers from 1 to n – Something very specific to Stack. No logic given but just the steps to follow. Just keep in mind that something of this sort exists. We are not solving this.