CareerCup

It was a phone interview. i proposed using a hash table with the priority as the key and each cell storing a queue of nodes. I could not solve the dequeue part in O(1) time. The interviewer mentioned that i was almost there. i havent figured out the answer though.

Vairaghi, what was your solution to this question?
Was it an on-site interview or phone interview?
Thank you.

For dequeue:

Checking the end of a list can be done in O(1). Checking the next priority is also O(1); the number of priorities is constant so the iteration will be O(1) or O(num priorites); essentially constant time.

Use heap to implement the priority queue, also have a variable to keep track of the maximum priority in the query. For every insertion, only compare the inserted element with that variable, thereby reducing the number of comparisons.

I think this is how the Linux2.6 kernel does it:
Have a doubly-linked list for each priority level. The head of each linked list can be stored in a hash, key's being the priority level, values being the head of the list.

How about using linked list and hash map together ? i.e. a linked list to enqueue in O(1) time and while dequeing, find the element in O(1) time using hash map which has the address of the lined list and address of node. You delete the node in O(1) time.

So essentially we can have both the operations in constant time.

Please correct me if I am wrong. Your comments are appreciated.

if the main is to support enqueue and dequeue in O(1) and get the highest pri in O(1)...will this work...

keep 2 queues...
one queue where we add from one end and remove from other...call this Q...
another whose top always has the highest pri element...call this PQ

here are add, delete and getHighPri methods...


enquee(obj o)
{
Q.addFront(o);

if (PQ.isEmpty())
PQ.addFront(Q)
else
if ( o.pri > PO.front().pri)
PQ.clear
PQ.add(o);
else
PQ.add(o)

}


getHighestPri()
{
return PQ.front()
}

dequeue()
{
object todeque = P.dequeue;
if (todeque == PQ.front)
PQ.dequeue;
}




p 10 11 9 15
pq 9 15

# Use a singly linked list to represent the queue that would hold the items according to their priorities.

# Since we have constant number of priorites (say 1 to 10), we can have an array of structure(of the type mentioned below) that would give us the hint where to insert an item in the linked list.

struct sub_pq {
Node* first;
Node* last;
};


Enque: Look in the array for 'last' node for the given priority, and insert next to it. If there is no item with this priority already in the list, then look for 'last' of higher priorities and/or 'first' of lower priotities, and then insert the item at it's appropriate position.
Then update the corresponding array element accordingly. O(1)
Deque: Remove first item from the linked list, and update the corresponding array element accordingly. O(1)