An interview question that is becoming popular (apparently British Petroleum folks have been asking in their interview) is design LRU cache. The catch is - each item has a TTL & a certain priority specified while the key, value is put into the cache. The eviction policy when cache is full is in the order
- evict all (or just the oldest expired value) based on TTL, if this makes space, good enough
- if nothing to evict as nothing has expired, remove the one with the lowest priority
- if there are multiple items with the lowest priority, remove the one that was accessed the first
The problem is pretty hard to even come up with a solution in an hour. You also need to write code of whatever solution you could find. The tradition LRU cache is designed as hashmap & a doubly linked linkedlist. Doubly linked linkedlist helps because the access time of keys are linear & you need to move the accessed key to the top of the linked list & remove the oldest item.
In this case, put the TTL aside for a moment. Lets look at priority & access time. You could get the same key, value 'put' operation but with a different priority. So the latest accessed item might not be on the top of the list. Hence a linked list will not help. A min-heap can. If we put a min-heap of [priority, key] tuple & hashmap of key -> value, we can pop from the min heap for the lowest priority for eviction & eventually remove the key from the hashmap.
For the case, when we have multiple items with same priority, we need to remove the oldest accessed key. The modified priority can be {priority}.{access timestamp}. Eg. 10.12345456 - where 10 is priority & 12345456 is the timestamp of access. The older value will have smaller timestamp & hence the net priority of it would be lower.
In case of a key getting put with different value or priority, or if the key gets accessed, the min-heap key is going to change. So we keep reference of the min-heap node in the hashmap, something like key -> value, priority, min-heap-node-ref . The min-heap-node-ref is generated when we enqueue the node in the min heap. In case of change of value / priority / access time (basically get), we removed the node from the min-heap & enqueue a new node in the min-heap & update the reference in the hashmap.
To implement TTL - the requirement is - we need to find if any of the keys expired (current time > put time + TTL). To find this, if we keep a sorted list of 'put time + TTL' when the key is put, we can then do O(1) operation to find if the oldest 'put time + TTL' is < current time. If yes, we remove it. For removing, we will need reference to the hashmap, basically the key. From the key, we can also remove the node from the min-heap.
During put, a key can be enqueued with the 'put time + TTL' that could be in future. We need to iterate through all the 'put time + TTL' so far & insert this new value. This can be efficiently done if we have sorted list or a BST.
If the same key is put with a different TTL, the BST node need to be removed & a new node need to be added. For O(1) removal, we can keep the reference of BST node in hashmap.
Final Data Structure
- min-heap of
[{priority}.{access timestamp}, key]tuple with heap operation on the first item of the tuple. - BST with each node is arranged based on 'put time + TTL' & containing the key for the reference to the hashmap
- hash map as
key -> {value, priority, min-heap-node-ref, bst-node-ref}
get complexity - O(logn)
- O(1) to access from hash map
- O(1) for removal from min-heap, rebalance min-heap - O(logn)
- O(logn) for adding new node to min-heap
put complexity (assuming eviction) - O(logn)
- check oldest item & remove from BST if required, rebalance BST - O(logn)
- get the removed key from BST or min-heap (min-heap operation is O(1)), remove the node from min-heap & rebalance - O(logn)
- insert node in hash map - O(1)
put complexity (assuming update to existing key) - O(logn)
- remove min-heap node if priority is updated, rebalance & add new node - O(logn)
- remove BST node if TTL is updated, rebalance & add new node - O(logn)
- update hashmap - O(1)
Hope this helps. Feel free to leave a comment if something does not seem right.