## Directi Interview Question

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

Use two stack to simulate queue. Implement findMax on stack.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

this enqueue isn't O(1) time. Its O(N), where N is the size of M

Comment hidden because of low score. Click to expand.
0

Isaac, it's not. Rather it's amortized O(1)

Comment hidden because of low score. Click to expand.
0

@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).

Comment hidden because of low score. Click to expand.
0

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 ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

What do you do when the maximum element is dequeued?

Comment hidden because of low score. Click to expand.
0

This is an open problem for worst case O(1). Solution using stacks is probably the best known so far (amortized O(1)).

Think again.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I dont know. But all this; is it just not the purpose of a max heap ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)
}

int pop()
{
int t=queue.pop();
if(t==arr.get(0))
{
arr.remove(0);
}
return t;
}

int max()
{
return arr.get(0);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done in O(1) using an extra queue to store the max element.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

#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;
}
}
}

Comment hidden because of low score. Click to expand.
0

@Nayak: Can you write your logic step by step ?

Comment hidden because of low score. Click to expand.
0

Taking an extra pointer called maxpointer which always points to the maximum element of queue. Look at case 4.

Comment hidden because of low score. Click to expand.
0

Just wanted to point out.. Your max function has complexity O(N). Think about the case when maximum element has been dequeued.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.