Amazon Interview Question Software Engineer in Tests
A Queue can be implemented as a pair of back to back stacks. Lets say we have the following elements in the queue : 1 2 3 4 5 6 7 8 9. We can represent this as two stacks P = 1 2 3 4 5 and Q = 6 7 8 9. The top of P is at 1 and the top of Queue is at 9. In an enqueue operation, the element is added into P. While in a dequeue, an element is removed from Q. Every element in P maintains the min when it arrived, and every element in Q maintains the min behind it. Thus finding the min is only going to compare top's min pointers of P and Q and can be found in O(1) time. Each enqueue takes O(1) time as we can enqueue into P and each dequeue takes O(1) time as we can remove from Q. But the problem is, when we do a dequeue operation from Q and we find Q to be empty, we will be required to copy all the elements of P into Q and update corresponding min pointers. This takes O(n) time. But from an amortized perspective, this slow operation is paid by the enqueue operation. By the accounting method, when we insert an element, we spend 3 dollars of charge - 1 for the actual enqueue operation, 1 to get copied into Q (Please note that an element gets copied into Q from P only once) and 1 for the dequeue operation. Hence we have the following running time guarantees -
Enqueue - O(1) Amortized
Dequeue - O(1) Amortized
Min - O(1) Worst case
Amortized O(1) can be had by maintaining one doubly-linked list for the queue and another for the sequence of queue entries that are larger than those behind them. With this scheme we may have to delete a bunch of crap from list #2 (but everything is inserted at most once, so it's still amortized O(1)).
I have no idea at the moment how to get worst-case O(1).
Just maintain the max_next node pointer in each node and adjust the pointer while performing enqueue and dequeue.
Just a pseudo code:
struct node{
int d;
node *next;
node *max_next;};
node *max_node;
//its just a pseudo code
void dequeue()
{
tmp=new node;
if(tmp->d > max_node->data)
{
tmp->max_next=max_node;
max_node=tmp;
}
Similarly we can write dequeue method.
since the constraint does not talk about restrictions on extra data structures, we can use a max heap to keep track of max element in the queue.
Every time u enqueue, heapify - if enque'd element is bigger than other elements , it will float to the root, every time u deque, remove the corresponding element from heap (O(n) for searching it). And anytime u want the max, its the root of the heap (O(1)).
Building heap(while enquing) is n times log n so nlogn.
Thats good enough. But if everything seems to be O(1) then we need to change gears. Possible solution could be use two queues - even a single queue is doable - with O(1) complexity for all operations.
One extra element space O(1) for remembering the max element.
If a new element comes - check against max to see if this is the new max. Update max.
If an element goes out, cross check the whole queue to find the new max element. Update max.
Do this make sense?
since on dequeue you are checking the entire queue so looks like its not O(1). Instead i feel the answer posted in the third post by Anonymous looks doable. Moreover, right now it looks that a single Doubly-linked list would do the job and yes it would be O(1) on an amortized basis.
u can maintain 2 queue one for maxele and normal ele
operations in first queue (contains all elements){
normal enqueue and normal dequeue;
}
operations in second queue {
enqueue : whenever u enqueue in first queue and if element in front of this queue is smaller then element beeing inserted...(insert the element at first in second queue other wise dont insert)
dequeue : whenever u dequeue in first queue and if element removed from first queue is equal to first element in second queue then remove element from this queue too...
}
idea is whenever we insert in oringal queue we are maintianing list of max in another queue so tat we need not change the structure of node... rather then single max maintained by becga...
Solution is pretty simple. We ourself make things complex by not looking at the simple side of it.
1.) Doubly linked list for queue.
2.) Keep max along with each node till that node.
Let say the queue is
2 ->8 ->6 ->9
struct{
int data
int max
struct * next
struct *prev
}
when 2 inserted, queue will be
(2,2)
when 8 inserted, queue will be
(2,2) -> (8,8)
when 6 inserted, queue will be
(2,2) -> (8,8) -> (6, 8)
when 9 inserted, queue will be
(2,2) -> (8,8) -> (6, 8) -> (9,9)
Here all operations are O(1)
my idea is to use a priority queue, ie a heap, in fact a max heap. a max heap is a tree like structure where the root of the tree (heap) is the maximum element.
so for example a heap (nothing but a complete binary tree except lower level) is like this
55
50 45
18 35 40 39
17
50 and 45 children of 55
18 35 children of 50
40 39 children of 45
17 child of 18
if you see the tree, it is completely filled except the bottom level (which is nothing but a heap, in this case a max heap with the maximum element at root)
Now simply do an array implementation
the array would be 55 50 45 18 35 40 39 17
max element---is arr[0]
dequeue---remove first element and check for the next biggest element. This is not that difficult...remember percolate down approach
enqueue is always done at the end of the array but again maintaining heap structure and order property
I think what the interviewer wants boggles down to implementation of a max priority queue i.e a max heap
This is simple. Every time u enQ, check max value. If greater, update max value. Else, dont change max. U can get max element in just O(1). Space is O(1) for the max element.
@helper: if u maintain just the max value, if u dequeue it then what will be the max value? so I think max heap is the best solution
There are two possible approaches..
1)By maintaining a max_next node pointer that would store the maximum value of the nodes below it. This value is updated upon enqueue depending on the value of the node enqueued. This takes O(1) time.
Cons: If there is a large volume of data, this may be inefficient because we might have to store a pointer for each node - causes redundancy.
To overcome this, if we are allowed additional storage, then we could go in for an alternate solution.
2) Use another data structure Stack. Every time a node is enqueued, check its value with the value of the node in the Stack. If it is greater, then push this node into the stack. If the value is lesser, then do nothing. To find the maximum element, just do a pop from the stack and that would return the maximum value. This operation takes O(1) time.
both of your approaches share the same idea. but I guess it doesn't work.
like approach 2.
what if the element with max value is dequeued? you will pop the max from stack as well, then what? how will you find the next max? do you mean the next max will be the next top element in the stack?
no, the next top element in the stack is enqueued before the max element you just popped out.so it's already gone before, this element is no longer in the queue.
let me know if i misunderstood your idea
i think this should work
maintain a doubly link list for max numbers.
while inserting a number in queue ,if it is greater than the current max insert it at head of the DLL. and maintain a pointer from the node in queue to this node in DLL
while deque, if the number to be dequed has a pointer to a node in max DLL delete the node from DLL ( can be done in O(1) as it is a DLL and pointer to the node is known) and deque the number.
max at any point is the number at head of DLL.
The extra stack and extra Q think wont work.
Consider the Queue:
-10 -30 -20
front rear
If you have a Stack and add elements to it if they are greater than present MAX
then STack would have -10 ONLY.
Now after dequeue, the largest element is -20 and its not in that Stack.
Neither the Queue would work.
I think use a MAX HEAP or use a priority Queue.
Logically every element in the given Queue is a contender to become the MAX. So insert each element in a decreasing priority Queue. Now the MAX operation would be O(1) because you need to dequeue the priority queue just once :)
However the enqueue/dequeue operations would be cumbersome!
<pre lang="" line="1" title="CodeMonkey43615" class="run-this">/*This is a running code. Just dont try to overflow buffers here. Very primitive
error correction mechanisms. The front of queue points to one element BEFORE actual
front. Rear points to rear elements.
Code works. Except when you empty the max queue. So try to be reasonable.
*/
#include <stdio.h>
#define MAXQ 100
typedef struct{
int items[MAXQ];
int front;
int rear;
}queue;
void enqueue(queue *pq, int val);
void dequeue(queue *pq, int *val);
int main(){
queue mainq, maxq;
mainq.front=mainq.rear=maxq.front=maxq.rear=0;
int choice,val;
int temp;
int first=1;
while(1){
printf("\n1. Enqueue \n2. Dequeue\n3. Maximum Element\n");
scanf("%d",&choice);
switch (choice)
{
case 1:
scanf("%d",&val);
enqueue(&mainq,val);
if(first)
{
enqueue(&maxq,val);
first=0;
}
else if (maxq.front!=maxq.rear) {
if(maxq.items[maxq.front + 1]<val)
maxq.items[maxq.front + 1] = val;
else
{while(1)
{
temp=maxq.items[maxq.rear];
if(temp<=val)
{maxq.items[(maxq.rear)--];}
else
{
enqueue(&maxq,val);
break;}
}
}}
break;
case 2:
dequeue(&mainq,&val);
if(val==maxq.items[maxq.front + 1])
dequeue(&maxq,&temp);
break;
case 3:
printf("\n\nMAX IS: %d ", maxq.items[maxq.front + 1]);
}
}
}
void enqueue(queue *pq, int val){
if (pq->rear==(MAXQ-1))
{pq->rear=0;}
else
(pq->rear)++;
if(pq->rear==pq->front)
{printf("\nOverflow!");
if(pq->rear)
(pq->rear)--;
else
pq->rear=MAXQ-1;
//printf("\nFRONT: %d REAR: %d",pq->front,pq->rear);
}
else
{pq->items[pq->rear]=val;
//printf("\nFRONT: %d REAR: %d",pq->front,pq->rear);
}
}
void dequeue(queue *pq, int *val){
if(pq->front==pq->rear) {
printf("\nUndeflow!");}
else
if(pq->front==MAXQ-1) {(pq->front)=0;}
else{
(pq->front)++;
*val=pq->items[pq->front];
//printf("\nFRONT: %d REAR: %d",pq->front,pq->rear);
}
}
</pre><pre title="CodeMonkey43615" input="yes">
</pre>
My option is to implement the queue with a Heap so that max can be easily maintained with enqueue and dequeue operations.
- Anonymous March 09, 2010