UPPCL'13

Question

How many number of add and remove operations are required to access x/2th element of a queue of ‘x’ elements, so that the original queue remains the same after the access is
1) 8*x
2) 4*x-1
3) 4*x
4) 8*x-1

Answer 1

Assume that i have 5 elements 1 2 3 4 5
Queue 1 hold this 1 2 3 4 5
Queue 2 is empty
if x = 5 then x/2 = 3

Now Initially queue1 : 1 2 3 4 5 queue 2 ---
Remove 1 from Q1          Q1 : 2 3 4 5
Insert 1 into Q2            Q2 : 1

Remove 2 from Q1          Q1 :  3 4 5
Insetr1 2nto Q2            Q2 : 1 2

Remove 3 from Q1          Q1 :   4 5 // displayed but this is not to be counted

Remove 1 from Q2       Q2 : 2
 Insert 1 into Q1       Q1 : 4 5 1

Remove 2 from Q2       Q2 :
 Insert 2 into Q1       Q1 : 4 5 1 2

Remove 4 from Q1          Q1 :  5 1 2  
Insert 4  into Q2            Q2 :  4

Remove  5 from Q1          Q1 :   1 2  
Insert 5  into Q2            Q2 :  4 5

Remove 4 from Q2            Q2 : 5
Insert 4 to Q1               Q1 : 1 2 4

Remove 5 from Q2            Q2 :
Insert 5 to Q1               Q1 : 1 2 4 5

Counting number of insertion and deletion = 16 = 4*(x-1) = 4*4 = 16

Comments

@rude : I tried it by single queue only first . I was getting 2*x-1. i was not closed to any of the option . So i first posted the answer for 2*x-1 only . But then later i thought of queue which gave me options . For 5/2 : No one has said me , i just took an array of 5elements . and middle element is 3 And if i take second queue in consideration then those are the required insertion and deletion and not too many insertion and deletion

---

@rude with one queue how is it possible ? we will always require one more queue, until and unless initially size of queue = number of elements in Q = x.

---

@Lord_Krishna Gurudev, this is a shit question, do not waste your time here.

And yes we can solve this problem by using without any extra queue..

Let delete (x/2) element from front and same time insert them from rear ( it will take x/2+x/2 operation)

Now access the middle element from the and.. again start deleting rest of (x/2) elements and start inserting that in the same queue. ( it will take x/2 + x/2 operation. ) and your problem will be solved in just 2*x operation. Which is not an option.