Priority Expiry Cache Problem

We all have heard of the often repeated Least Recently Used (LRU) Cache problem asked in interviews. The problem is trivial once you realize that a hash table and a doubly linked list can be used to solve it efficiently. We'll work on a variant of the LRU problem. The intent of this problem is to exercise our minds to be able to compose various data-structures to achieve desired worst-case complexity for various operations. Without further ado, the problem is presented below:

The PriorityExpiryCache has the following methods that can be invoked:

• get(String key)

• set(String key, String value, int priority, int expiry)

• evictItem(int currentTime)

The rules by which the cache operates is are follows:

1. If an expired item is available. Remove it. If multiple items have the same expiry, removing any one suffices.

2. If condition #1 can't be satisfied, remove an item with the least priority.

3. If more than one item satisfies condition #2, remove the least recently used one.

And it goes without saying that we have to design our function implementations to be as fast as possible.

Let's start with the get() method. Given a key we need to return the associated value. The fastest way we can implement a retrieval operation is to use a hash table. The insertion and retrieval times would both be O(1). Besides the key and the value provided to us, we'll need to store the expiry time and the preference. So Let's create a class Item that holds all these three artifacts associated with the key.

class Item {
    int preference;
    int expireAfter;
    String key;
    String value;
}

We can now create a hash table using the Item.key and the value as the item object itself. It should look like as follows:

We can serve get() requests using the above hashtable in O(1). Whenever a get is invoked, we have to capture the notion of an item being most recently used. Hold onto that thought for now as we'll solve it once we create the other needed data-structures.

Let's start rule#1 which says that an expired item should be removed first. We need to find the item with the minimum expiry time. Whenever you hear yourself looking for the maximum or the minimum among a set of values, your likely choice of data-structure is a heap (called a priority queue in some language implementations) as it provides O(1) look-up (not removal) for minimum or maximum value. A max-heap can be used for looking up maximum values while a min-heap can be used for looking up minimum values. For our case, we can create a min-heap of the objects of class Item. The min-heap is predicated on the expireAfter variable, i.e. the min-heap is built based on the value of expireAfter variable for each object. Conceptually, the min-heap looks like as follows:

When evictItem() is invoked, we peek at the top of the min-heap and see if the item with the minimum expiry time is indeed expired. If so we pop the top of the min-heap and also remove it from our hashtable. Removing the minimum item from the min-heap is O(lgn) and removal from the hashtable is O(1). The total cost thus far is O(lgn) +

$$O(lgn) + O(1) = O(lgn)$$ ...