2

I was practicing this question for an Interview .

Best data structure that will implement the following 3 operation in minimum time::

a.) insertion.
b.) removing the oldest element.
c.) printing the largest element.

The Best that, i can think of is a Min/Max Heap or a priority Queue. For operation (a) and (c) ,Heap is efficient but, I am not sure, the second operation 'removing the oldest element' can be done efficiently using Heap.

So Suggest an ideal data Structure that will implement all 3 operation efficiently.

Thanks!

Ritesh Kumar Gupta
  • 5,055
  • 7
  • 45
  • 71
  • Conceptual question about programming and data structures in general could also be asked on http://programmers.stackexchange.com/. – Some programmer dude Jul 27 '12 at 06:58
  • what do you mean by removing the oldest element?. What does old refer to here? In some sense it is also a min/max element – arunmoezhi Jul 27 '12 at 07:22
  • @arunmoezhi I think he meant the element that was inserted first between all the elements in the data-structure. – barak1412 Jul 27 '12 at 07:27
  • still the question is unclear. What are the frequencies of these operation. – arunmoezhi Jul 27 '12 at 07:43
  • 1
    All in O(1): http://stackoverflow.com/questions/4802038/implement-a-queue-in-which-push-rear-pop-front-and-get-min-are-all-consta?lq=1 –  Jul 27 '12 at 09:06
  • @Gaurav: I'm not sure about it - how will you in O(1) update current maximum if the maximal element is the oldest one, being deleted ? – Grigor Gevorgyan Aug 02 '12 at 08:18

2 Answers2

3

What about using some kind of max heap for operations a,c and just an additional queue of nodes, storing them in historical order ? If you use Fibonacci Heap, you'll get O(1) time for operations a and c, and O(logN) time for b. You just need to push pointers to new nodes into queue when adding new element, and delete the node pointed by queue front when deleting oldest element (with poping it from queue of course).

Grigor Gevorgyan
  • 6,753
  • 4
  • 35
  • 64
1

i think with oldest he means the insertiontime and the laregest element is the element with the highest value. Maybe you can it write as Tupels of (value,insertiontimes)

maybe you can insert all elements in a max heap for values and in a min hear the insertiontimes and connect them. In my mind is there 2 heaps which are connected and the pairs are the representation of the tupels. it isnt really elegant but it should works. after each insertion and deleation you need to check for the heap-properties.

Aruscher
  • 153
  • 1
  • 10