Explain the data structure you would use to implement pop() and push(Object, int) for a Priority Queue.

Question

Anonymous · Accepted Answer

No ... I did mention it in my review. Interviewed and No offer.

John Feng · Answer

Heap is the one to choose. Priority queue always pops out the highest valued element(the highest value is defined using weak ordering criterion), pop_heap will make sure the second highest element is placed on top after the first one is popped out, push_heap will also make sure the highest value is placed on top of the queue. 

In many cases, this is all you want - the highest valued element, which is what priority queue is operating on..

Anon · Answer

Did you get the job?

Anonymous · Answer

I would use a linkedlist here. I will maintain the linkedlist in a descending order/ The add() method will intake a node and it loops from root and postions in appropiate position O(n)
Peek or poll returns the root element.

Anonymous · Answer

I had said red black tree. He seemed to agree

Anonymous · Answer

Would a heap not be more appropriate?

Jordan · Answer

I got this question as well.  However, the answer is impossible in constant time.    A self balancing tree is one way to implement this.  In that scenario you have O(log n) time for insertion and removal.  You can always have the get minimun in constant time.  A van Emde Boas tree or Fusion Tree can speed up this time, but not bring it to constant time.

Amazon

Amazon Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches