Adobe Interview Question
Computer ScientistsCountry: India
Interview Type: In-Person
use heap to heapify the elements of the queue..i,e when you enQ put in heap, the max can be retrieved from max heap in O(1). when u deQ, deQ it from the heap also.
So enQ is O(logn), deQ is O(logn) and findMax is O(1).
int arr[n],n=0,c=0;
enqueue()
{
scanf("%d",c);
for(i=n;i<0;i--)
arr[n+1] = arr[n];
arr[0] = c;
n++;
}
dequeue()
{
free(arr[n]);
n--;
}
findmax()
{
c = 0;
for(i=n;i>0;i--)
if( c < arr[n]){ c = arr[n];}
printf("max = %d",c);
}
voidmain()
{
printf("enter number to insert or delete or find max -1 to exit");
scanf("%d",c);
if(C!=-1)
queue()
{
if(c ==1)
enqueue();
if(c==2)
dequeue();
if(c==3)
findmax()
else{
printf("enter number to insert or delete or find max -1 to exit");
scanf("%d",c);
queue();
}
}
we can also implement it by the use of two queues,one cud be used as the normal queue and the other cud be used as the queue for storing the maxelements...
but when you implement such functionality using another queue, you will not get max value all the time. With stack it works properly.
for example take queue data - 2 7 5 13 7 and maxqueue will have - 2 7 7 13 13. When you dequeue both queues for getting max value - the last values of the both queues will have end values as 7 and 13 resp. There is the issue.
Instead of storing the values straight away create an object with something like
class Data
{
int number;
int maxValue;
}
Queue<Data> q = new LinkedList<Data>();
Every time you store your values, store it as this Data object
so
enqueue(int value)
{
Data data = new Data();
data.number = value;
if(data.maxValue < value)
data.maxValue = value;
}
What this does is it stores the findMax at each point of the data insertion, so you can access the maximum data at each point looking at the top of the queue.
what will be the implementation of dequeue() function then. I mean
what if the number to be dequeued is the MAX. i guess maintaining a sorted datastrructire like max or min heap could suffice.
If it were a Stack, then using two stacks would have made sense. But since it is a queue and queue is a FIFO (not a LIFO). You may use a single variable to keep track of the max and at each insertion compare the new element with max and update max accordingly. If a dequeue is performed, the element that was inserted first will be removed. finding max will be O(1) time.
I think using a stack will work
everytime u insert a new element to a queue, do the following
if element is less than top of the stack then push it
if it is more than top of the stack then pop the stack until a value larger than the element is reached.
reverse the stack
that's it.
example
enqueue the following one by one and observe the stack
4 6 9 3 7 2
queue
4
6 4
9 6 4
3 9 6 4
7 3 9 6 4
2 7 3 9 6 4
Stack
4
6
9
3 9
7 9
2 7 9
Reverse the stack and now do the dequeue
if a max is dequeued then pop the corresponding value from the stack
queue
2 7 3 9 6 4
2 7 3 9 6
2 7 3 9
2 7 3
2 7
2
Revered Stack
9 7 2
9 7 2
9 7 2
7 2
7 2
2
Top of the stack is the max of the queue
remember to reverse back the stack every time you enqueue an element.
Use a queue which will have enqueue() and dequeue() operations.
- CoolGeek March 02, 2012Also, there would be a stack which would contain all max elements encountered till now.
Whenever an element is being enqueued, and it is greater than current max (top of stack), it will be pushed on stack also.
If a no. 'k' is current max and 'k' comes for enqueueing once again we will push 'k' once more on stack.
Whenever we dequeue an element, we check if it is same as element on top of stack. If it is same pop the element from stack as well.