Directi Interview Question
Country: India
Interview Type: Phone Interview
I'm not sure how you would find the maximum using two stacks. Here's a solution using a double ended queue. Let:
- D : be a queue of elements
- M : be a deque. The maximum of elements in D will always be the front element of this queue (that's our invariant).
We always enqueue and dequeue elements in D when requested. We don't enqueue in M always. We always ensure that if the front of M is the element being dequeued, we dequeue it as well. If that happens, the largest element is deleted, and the front of M should now be the second largest element. This tells us that M (if seen from the the front), should always contain the maximum element till the point it occurs in D.
function enqueue (x):
D.enqueue(x);
while (!M.isEmpty() && x > M.rear()) {
M.dequeue_rear();
}
M.enqueue(x);
The deque is assumed to supported the following operations:
-enqueue: enqueue at the rear of the queue
-dequeue: dequeue from the front of the queue
-dequeue_rear : dequeue from the rear of the queue
@dr house: Can you implement a stack which supports O(1) findMax?
Now if you simulate a queue using two such stacks, how difficult do you think it is, to find the max of all elements in the queue? (i.e. consider both stacks).
okay. I havent understood what u both talked about. I'm sorry.
But my take on the question was:
a queue with the Data structure :
struct node
{
int data;
node *order;
node *predecessor;
node *successor;
};
now 3 pointers pointing to start,end and the max position.
the nodes will be arranged in a descending order, with the help of an appropriate add function.
what say ?
FindMax and Insert can be done easily as we can maintain to reference to max element and Max element will be for all the elements of the Queue.
To work with delete, use hashing too, Whenever you get and value add it to queue and Hash( value , address of the value in queue). To delete check in hash if value exist then you will get a valid address , just delete that node.
Assumption - We are implementing a simple Queue using list structure.
push(int data)
{
queue.push(data);
// arr is an ArrayList here
while(data> arr.get[arr.size()-1] && arr.size()!=0)
{
arr.remove[arr.size()-1];
}
//the removal above will become amortized O(1)
arr.add(data);
}
int pop()
{
int t=queue.pop();
if(t==arr.get(0))
{
arr.remove(0);
}
return t;
}
int max()
{
return arr.get(0);
}
#include<stdio.h>
main()
{
int a[100],i;
static int last = 0,first = 0,qptr;
int max = 0,ch,element;
while(ch != 5)
{
printf("enter the choice : 1.insert, 2.delete, 3.print, 4.max, 5.exit:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("Enter the element to insert:");
scanf("%d",&element);
a[last] = element;
if(max < element)
{
qptr = last;
max = a[qptr];
}
printf("qptr = %d\n",qptr);
last++;
break;
case 2:
if(first == last)
{
printf("Que is Empty\n");
break;
}
else
{
first = first+1;
if(first > qptr)
{
qptr++;
max = a[qptr];
}
}
break;
case 3:
if(first == last)
{
printf("Que is Empty\n");
break;
}
else
{
for(i=first;i<last;i++)
printf("%d ",a[i]);
printf("\n");
}
break;
case 4:
if(first == last)
{
printf("Que is Empty\n");
break;
}
else
printf("max = %d\n",max);
break;
case 5:
break;
}
}
}
Taking an extra pointer called maxpointer which always points to the maximum element of queue. Look at case 4.
Use two stack to simulate queue. Implement findMax on stack.
- Anonymous October 02, 2012