Problem Statement: Design Priority Expiration LRU Cache.
Description:
Least Recently Used (LRU) Cache is a very common problem asked in interviews. Take a look here if you want to know more : https://leetcode.com/problems/lru-cache/
As we know LRU Cache has these rules:
- It has a maximum capacity to hold items.
- Each cache key has a corresponding value.
- If there is a cache set/get, the item becomes most recently used.
- If the cache becomes full and a new item is pushed, there is an eviction policy to remove the least recently used item first and then push the current item.
The key to solve the problem is to realize that a hash table and a doubly linked list can be used to do get/set operation efficiently in constant time.
However PE LRU Cache has been asked in some recent interviews at Tesla[1], British Petroleum[2] etc.
Lets see what is it?
The Priority Expiration LRU Cache has additional constraints:
- When adding an item to the cache, each key is accompanied by its respective value, priority, and expiration time.
- Should the cache reach its capacity, the eviction policy comes into effect, leading to the removal of the entry with the earliest expiration time.
- In cases where multiple keys share the same expiration time, any of them could be chosen for eviction.
- If there are no items with the given expiration time, the eviction process targets the item with the lowest priority.
- When several items share the same minimal priority, the one that has been least recently used is selected for eviction. It's worth noting that the least recently used item might not necessarily possess the lowest priority.
Lets take the example as posted in one of the interview questions posted above:
GetExpiryThreshold() => returns a random value in range [0, 100000]
cache = new Cache(5)
cache.Set(key:"A", value:5, priority:1, expiry: 1000) // [A]
cache.Set(key:"B", value:15, priority:5, expiry: 500) // [B, A]
cache.Set(key:"C", value:0, priority:5, expiry: 2000) // [C, B, A]
cache.Set(key:"D", value:1, priority:5, expiry: 2000) // [D, C, B, A]
cache.Set(key:"E", value:10, priority:5, expiry: 3000) // [E, D, C, B, A]
cache.Get("C") // returns 0 // [C, E, D, B, A]
cache.Set(key:"F", value:15, priority:5, expiry: 1000) // since cache is full here expiry threshold applies, ex- if it returned 600, then B gets evicted and F gets inserted
// [F, C, E, D, A]
cache.Set(key:"G", value:0, priority:5, expiry: 2000) // again assume threshold returned 600 then none of the items expired, so the least priority item i.e. A gets evicted and G inserted
// [G, F, C, E, D]
cache.Set(key:"H", value:1, priority:1, expiry: 2000) // assuming threshold as 600, here none expired and all items have same priority, so least recently item D gets evicted
// [H, G, F, C, E]
cache.Get("D") // throw exception as D is not present in cache
cache.Set(key:"I", value:10, priority:2, expiry: 2000) // assuming threshold is 2000, the oldest expired item is F:1000, it gets evicted and I inserted
// [I, H, G, C, E]
cache.Set(key:"E", value:10, priority:2, expiry: 2000) // since E is already there no eviction
// [E, I, H, G, C]
cache.Set(key:"M", value:10, priority:1, expiry: 3000) // asuming threshold as 2000, all the items have same expiry so least priority H will get evicted
// [M, E, I, G, C]Solution:
If we focus solely on the LRU aspect of the problem, we can employ a combination of a hash map and a doubly linked list to address eviction rules, achieving constant time complexity (O(1)) for both the get and set operations.
However, due to the need to prioritize eviction based not only on the least recently used item but also on factors like expiry and priority, the approach needs to change.
For better efficiency, it is required to identify expired items quickly, ideally performing in constant time. One way to achieve this is by organizing items in a sorted manner based on their expiry time as key. A map can be utilized to better both insertion, deletion and lookup operations, maintaining logarithmic efficiency.
Also because multiple items can share the same expiry time, a list of keys with identical expiry times can be stored within the map. Additionally, the insertion and deletion for items with the same expiry time can be optimized using a hash set. It is required for removing any of the items with identical expiry in constant time. Note that in case of equal expiry time, we need to delete any one of these items. So our approach will handle it in logarithmic time only.
Expanding on this concept, a similar approach can be employed to manage item priorities, ensuring efficient insertion and lookup operations. As for handling the eviction of least recently used items, the previously established solution used for a standard LRU cache can be retained.
Importantly, it's worth noting that situations might arise where items with lower expiry times remain in the cache after eviction. To address this, the solution can be modified to evict items from the front of the expiry time map if their expiry time is lower than that of the evicted item. This adjustment maintains the overall time complexity while accommodating cases with lower expiry times.
Implementation:
#include <bits/stdc++.h>
using namespace std;
/*
The problem statement requires us to design a cache with the following methods:
- 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.
4. Multiple items can have the same priority and expiry.
*/
struct CacheItem{
string key;
int value;
int priority;
int expiry;
CacheItem(string _key, int _val, int _prio, int _exp):
key(_key), value(_val), priority(_prio), expiry(_exp){}
};
class PELRUCache{
private:
list<CacheItem> pelruList; // doubly linked list of cache items
unordered_map<string, list<CacheItem>::iterator> umapPelruKeyCachePosition;
map<int, unordered_set<string>> mapPelruExpiryKeysSet; // sorted expiry time keys
map<int, unordered_set<string>> mapPelruPriorityKeysSet; // sorted priority keys
int capacity;
void DoEviction(string _key){
if(umapPelruKeyCachePosition.count(_key) == 0){
return;// not found in cache
}
auto itr = umapPelruKeyCachePosition[_key];
auto currItem = *itr;
umapPelruKeyCachePosition.erase(_key);
Clear(mapPelruExpiryKeysSet, currItem.expiry, _key);
Clear(mapPelruPriorityKeysSet, currItem.priority, _key);
pelruList.erase(itr);
}
void Clear(map<int, unordered_set<string>>& mapKeysSet, int itemValue, string _key){
auto itr = mapKeysSet.find(itemValue);
if(itr != mapKeysSet.end()){
if(!mapKeysSet[itemValue].empty()){
mapKeysSet[itemValue].erase(_key);
}
if(mapKeysSet[itemValue].empty()){
mapKeysSet.erase(itemValue);
}
}
}
void Insert(map<int, unordered_set<string>>& mapKeysSet, int itemValue, string _key){
mapKeysSet[itemValue].insert(_key);
}
int Count(map<int, unordered_set<string>>& mapKeysSet, int itemValue){
auto itr = mapKeysSet.find(itemValue);
if(itr != mapKeysSet.end()){
return mapKeysSet[itemValue].empty()? 0 : mapKeysSet[itemValue].size();
}
return 0;
}
string FindEvictItemKey(int expiryTime){
// in our expiry map we can get the threshold expiry time items in O(log n)
int expiredItemsCount = Count(mapPelruExpiryKeysSet, expiryTime);
if(expiredItemsCount != 0) return *(mapPelruExpiryKeysSet[expiryTime].begin());
// first item of least priority map can be found in O(log n) time
int leastPriorityItemsCount = (*(mapPelruPriorityKeysSet.begin())).second.size();
if(leastPriorityItemsCount == 1) return *(((*(mapPelruPriorityKeysSet.begin())).second).begin());
// multiple same priority items so just return the least recently used in O(1)
return (*(pelruList.begin())).key;
}
public:
PELRUCache(int _cap=5): capacity(_cap){}
int Get(string _key){
if(umapPelruKeyCachePosition.count(_key) == 0){
return -1;// not found in cache
} else {
// move the key to last of list to make it recent
auto olditr = umapPelruKeyCachePosition[_key];
auto oldItem = *olditr;
pelruList.erase(olditr);
pelruList.insert(pelruList.end(), oldItem);
auto itr = pelruList.end(); --itr;
umapPelruKeyCachePosition[_key] = itr;
// no need to update the expiry or priority maps
return oldItem.value;
}
}
void print(){
for(auto item : pelruList){
cout <<"["<<item.key<<","<<item.value<<","<<item.priority<<","<<item.expiry<<"] ";
}
cout<<endl;
}
void EvictItem(int currTime){
cout <<"Evict time:"<<currTime<<endl;
string evictItemKey = FindEvictItemKey(currTime);
if(evictItemKey.empty()) throw exception();
DoEviction(evictItemKey);
}
void Set(string _key, int _val, int _prio, int _exp){
if(umapPelruKeyCachePosition.count(_key) == 0){
if(!umapPelruKeyCachePosition.empty() && umapPelruKeyCachePosition.size() == capacity){
int currTime = 100 * (rand() % 100);// some random time
EvictItem(currTime);
}
} else {
auto olditr = umapPelruKeyCachePosition[_key];
int oldExpiry = (*olditr).expiry;
int oldPriority = (*olditr).priority;
Clear(mapPelruExpiryKeysSet, oldExpiry, _key);
Clear(mapPelruPriorityKeysSet, oldPriority, _key);
pelruList.erase(olditr);
}
// push the new item in cache
CacheItem currItem(_key, _val, _prio, _exp);
// add item at end of list, so that the least recently used item is at the front
pelruList.insert(pelruList.end(), currItem);
// get the position of item in cache list
auto itr = pelruList.end(); --itr;
// update hash map with item position in list
umapPelruKeyCachePosition[_key] = itr;
// update the expiry time map
Insert(mapPelruExpiryKeysSet, _exp, _key);
// update the priority map
Insert(mapPelruPriorityKeysSet, _prio, _key);
}
};
int main() {
PELRUCache cache(5);
cache.Set("A", 5, 1, 1000); cache.print();
cache.Set("B", 15, 5, 500); cache.print();
cache.Set("C", 0, 5, 2000); cache.print();
cache.Set("D", 1, 5, 2000); cache.print();
cache.Set("E", 10, 5, 3000); cache.print();
cout << cache.Get("C")<< endl; cache.print();
cache.Set("F", 15, 5, 1000); cache.print();
cache.Set("G", 0, 5, 2000); cache.print();
cache.Set("H", 1, 1, 2000); cache.print();
cout << cache.Get("D")<< endl; cache.print();
cache.Set("I", 10, 2, 2000); cache.print();
cache.Set("E", 10, 2, 2000); cache.print();
cache.Set("M", 10, 1, 3000); cache.print();
return 0;
}Output:
[A,5,1,1000]
[A,5,1,1000] [B,15,5,500]
[A,5,1,1000] [B,15,5,500] [C,0,5,2000]
[A,5,1,1000] [B,15,5,500] [C,0,5,2000] [D,1,5,2000]
[A,5,1,1000] [B,15,5,500] [C,0,5,2000] [D,1,5,2000] [E,10,5,3000]
0
[A,5,1,1000] [B,15,5,500] [D,1,5,2000] [E,10,5,3000] [C,0,5,2000]
Evict time:8300
[B,15,5,500] [D,1,5,2000] [E,10,5,3000] [C,0,5,2000] [F,15,5,1000]
Evict time:8600
[D,1,5,2000] [E,10,5,3000] [C,0,5,2000] [F,15,5,1000] [G,0,5,2000]
Evict time:7700
[E,10,5,3000] [C,0,5,2000] [F,15,5,1000] [G,0,5,2000] [H,1,1,2000]
-1
[E,10,5,3000] [C,0,5,2000] [F,15,5,1000] [G,0,5,2000] [H,1,1,2000]
Evict time:1500
[E,10,5,3000] [C,0,5,2000] [F,15,5,1000] [G,0,5,2000] [I,10,2,2000]
[C,0,5,2000] [F,15,5,1000] [G,0,5,2000] [I,10,2,2000] [E,10,2,2000]
Evict time:9300
[F,15,5,1000] [G,0,5,2000] [I,10,2,2000] [E,10,2,2000] [M,10,1,3000] Complexity analysis:
-
Time Complexity: As map operations set/get requires O(log n) in worst case. We have time complexity for Cache Set Operation as O(log n). Since we are only looking up any item and does not update the map at all while getting so Cache Get Operation as constant i.e. O(1). Similarily evict any item requires map operation for deletion which makes Cache Evict Item complexity as O(log n).
-
Space Complexity: As we are not using any additional space for other operations other than the cache space to hold n items so it is O(1).
Further improvement:
It's worth noting that the logarithmic time complexity attributed to both eviction and set operations stems from the adoption of a map for maintaining sorted items. Yet, we can achieve constant time complexity by exploiting the fact that priority and expiry time are integers, which has a fixed 32-bit representation. By creating a fixed-depth binary trie — set at 32 levels — it becomes possible to have item lookup or insertion in constant time (O(32) ~ O(1)). As a result, this approach allows us to do all operations with constant time complexity.
Implementation:
We need a binary trie node to hold the binary representation of expiry time and priority. So we can create a common data struture trie for both fo them and replace it in our original code above wherever map is used.
class PELRUTrieNode{
private:
unordered_set<string> setOfCacheKeys;
public:
vector<PELRUTrieNode*> child;
bool isEnd;
PELRUTrieNode(bool bit):child(2, nullptr), isEnd(false){
}
bool HasKey(string key){
return setOfCacheKeys.count(key) > 0;
}
void InsertKey(string key){
setOfCacheKeys.insert(key);
}
void DeleteKey(string key){
setOfCacheKeys.erase(key);
}
int KeysCount(){
return isEnd ? setOfCacheKeys.size() : 0;
}
string First(){
return isEnd && KeysCount()>0 ? *(setOfCacheKeys.begin()) : "";
}
};From the trie thus created should support constant time insertion, deletion and lookup for any key as well as the priority/expiry attribute.
class PELRUTrie{
private:
PELRUTrieNode *root;
public:
PELRUTrie(): root(new PELRUTrieNode(0)){}
// insertion of the
void Insert(int attributeValue, string cacheKey){
auto curr = root;
for(int i=31; i>=0; i--){
bool bit = attributeValue & (1<<i);
if(curr->child[bit] == nullptr){
curr->child[bit] = new PELRUTrieNode(bit);
}
curr = curr->child[bit];
}
curr->InsertKey(cacheKey);
curr->isEnd = true;
}
void Erase(int attributeValue, string cacheKey){
auto curr = root;
for(int i=31; i>=0; i--){
bool bit = attributeValue & (1<<i);
if(curr->child[bit] == nullptr){
return; // attributeValue does not exist
}
curr = curr->child[bit];
}
curr->DeleteKey(cacheKey);
if(curr->KeysCount() == 0){
curr->isEnd = false;
}
}
string GetFirstKey(int attributeValue){
auto curr = root;
for(int i=31; i>=0; i--){
bool bit = attributeValue & (1<<i);
if(curr->child[bit] == nullptr){
return "";
}
curr = curr->child[bit];
}
return curr->First();
}
int GetKeyCount(int attributeValue){
auto curr = root;
for(int i=31; i>=0; i--){
bool bit = attributeValue & (1<<i);
if(curr->child[bit] == nullptr){
return 0;
}
curr = curr->child[bit];
}
return curr->KeysCount();
}
// This method gets the least value by traversing the left most pointers from top to bottom
// it is beneficial in case of priority trie where we use this to get the least item in constant time
int First(){
auto curr = root;
int attributeValue = 0;
for(int i=31; i>=0; i--){
if(curr->child[0] != nullptr){
curr = curr->child[0];
}
else if(curr->child[1] != nullptr){
curr = curr->child[1];
attributeValue |= (1<<i);
} else {
return 0;
}
}
return attributeValue;
}
string FirstKey(){
auto curr = root;
for(int i=31; i>=0; i--){
if(curr->child[0] != nullptr){
curr = curr->child[0];
}
else if(curr->child[1] != nullptr){
curr = curr->child[1];
} else {
return "";
}
}
return curr->First();
}
};Now we can replace all calls of map operations by using the trie created above.
class PELRUCache{
private:
list<CacheItem> listOfCacheItems; // doubly linked list of cache items
unordered_map<string, list<CacheItem>::iterator> umapItemPositionsByKey;
PELRUTrie trieKeysByExpiration;// fixed depth binary trie for expiry items
PELRUTrie trieKeysByPriority;// fixed depth binary trie for priority
int maxCapacity;
void DoEviction(string _key){
if(umapItemPositionsByKey.count(_key) == 0){
return;// not found in cache
}
auto itr = umapItemPositionsByKey[_key];
auto currItem = *itr;
umapItemPositionsByKey.erase(_key);
trieKeysByExpiration.Erase(currItem.expiry, _key);
trieKeysByPriority.Erase(currItem.priority, _key);
listOfCacheItems.erase(itr);
}
string FindEvictItemKey(int expiryTime){
// in our expiry trie we can get the threshold expiry time in O(H) ~ constant time as H = 32 for 32-bit integer
int expiredItemsCount = trieKeysByExpiration.GetKeyCount(expiryTime);
if(expiredItemsCount != 0) return trieKeysByExpiration.GetFirstKey(expiryTime);
// first item of least priority trie can be found in O(H) ~ constant time as H = 32 for 32-bit integer
int leastPriority = trieKeysByPriority.First();
int leastPriorityItemsCount = trieKeysByPriority.GetKeyCount(leastPriority);
if(leastPriorityItemsCount == 1) return trieKeysByPriority.GetFirstKey(leastPriority);
// multiple same priority items so just return the least recently used in O(1)
return (*(listOfCacheItems.begin())).key;
}
public:
PELRUCache(int _cap=5): maxCapacity(_cap){}
int Get(string _key){
if(umapItemPositionsByKey.count(_key) == 0){
return -1;// not found in cache
} else {
// move the key to last of list to make it recent
auto olditr = umapItemPositionsByKey[_key];
auto oldItem = *olditr;
listOfCacheItems.erase(olditr);
listOfCacheItems.insert(listOfCacheItems.end(), oldItem);
auto itr = listOfCacheItems.end(); --itr;
umapItemPositionsByKey[_key] = itr;
// no need to update the expiry or priority tries
return oldItem.value;
}
}
void EvictItem(int currTime){
//cout <<"Evict time:"<<currTime<<endl;
string evictItemKey = FindEvictItemKey(currTime);
if(evictItemKey.empty()) throw exception();
DoEviction(evictItemKey);
}
void Set(string _key, int _val, int _prio, int _exp){
if(umapItemPositionsByKey.count(_key) == 0){
if(!umapItemPositionsByKey.empty() && umapItemPositionsByKey.size() == maxCapacity){
int currTime = 100 * (rand() % 100);// some random time
EvictItem(currTime);
}
} else {
auto olditr = umapItemPositionsByKey[_key];
trieKeysByExpiration.Erase((*olditr).expiry, _key);
trieKeysByPriority.Erase((*olditr).priority, _key);
listOfCacheItems.erase(olditr);
}
// push the new item in cache
CacheItem currItem(_key, _val, _prio, _exp);
// add item at end of list, so that the least recently used item is at the front
listOfCacheItems.insert(listOfCacheItems.end(), currItem);
// get the position of item in cache list
auto itr = listOfCacheItems.end(); --itr;
// update hash map with item position in list
umapItemPositionsByKey[_key] = itr;
// update the expiry time trie
trieKeysByExpiration.Insert(_exp, _key);
// update the priority trie
trieKeysByPriority.Insert(_prio, _key);
}
void print(){
for(auto item : listOfCacheItems){
cout <<"["<<item.key<<","<<item.value<<","<<item.priority<<","<<item.expiry<<"] ";
}
cout<<endl;
}
};Let me know your thoughts on further improvement or any other ideas / suggestions.
Thanks for reading! Happy coding.
References:
[1] https://leetcode.com/discuss/interview-question/1114869/Tesla-Phone-screen/880661
[2] https://leetcode.com/discuss/interview-question/3949761/British-Petroleum-or-Coding-Round