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: