Time expiration data structure

Question

On a recent coding interview I was asked to implement a key - value store data structure. implement

size() : Number of elements in the list.

find(key) : Return the value at the key, otherwise throw nosuchelement exception.

insert(key, timestamp) : Add or update the element with this key. If the list is full, then don't do anything.

• The list has a maximum number of elements that it can hold
• Every element is inserted as a key and a value, time duration after which it should not be considered as in the list, and the time stamp of the time it was entered.
• If the list is full, then ignore the element trying to be added, unless it is a duplicate key.
• If the element with the same key already exists, update the existing value and the existing time stamp
• Once the time exceeds the time stamp + duration of an element, then don't consider it to be part of the structure any more. This means that if the list was previously full, It is not full any more.

I was having trouble finding an efficient way to keep track of the elements that are still in the list considering that elements can be ejected from the list if their time has run out.

Answer 1

I think what you're looking for is an indexed priority queue. Basically, you build a min priority queue whose key is the timestamp. And you create an index (by key) that keeps track of item locations in the priority queue.

On every operation, you can remove expired items from the queue with something like:

while (pq.peek().timestamp < current_time) {
    pq.remove();
}

The complexity of that will be O(k log n), where k is the number of items you remove, and n is the total number of items in the queue.

There is an indexed priority queue implementation available at http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html. I've heard good things about it, but I've never used it myself.