# True O(1) C++ solution, hashtable + linked list, beating 90%

• The idea is to maintain all <key, value> pairs with the same frequency in the same bucket and we maintain a linked list of those bucket ordered by its frequency.

In side the bucket we maintain all <key, value> pairs sorted in insertion order and we use another linked list to make sure insertion/deletion operations will be constant.

To faster lookup the <key, value> pair, we maintain a hashtable keyed by the actual key and the value being Bucket and ListNode.

So essentially we have:

LFU cache holds:
Doubly linked list of buckets sorted by frequency: BucketNode*
unordered_map<int, pair<BucketNode*, ListNode*>> keyLocationTable

BucketNode holds:
Doubly linked list of ListNode* ordered by insertion order.

LiskNode holds:
<key, value> pair

``````class LFUCache {
private:
struct ListNode {
int key;
int value;
ListNode* prev;
ListNode* next;
ListNode(int k, int v) : key(k), value(v), prev(NULL), next(NULL) {};
};

struct BucketNode {
int freq;
ListNode* tail;
BucketNode* prev;
BucketNode* next;

BucketNode(int f) : freq(f), prev(NULL), next(NULL), head(NULL), tail(NULL) {};

void removeOne(ListNode* node) {
if (node == head && node == tail) {
} else if (node == head) {
node->next->prev = NULL;
} else if (node == tail) {
node->prev->next = NULL;
tail = node->prev;
} else {
node->prev->next = node->next;
node->next->prev = node->prev;
}
node->prev = node->next = NULL;
}

} else {
}
}

bool empty() { return head == NULL; }
};

public:
LFUCache(int capacity) : mCapacity(capacity) {
}

int get(int key) {
if (mCapacity == 0) return -1;
ListNode* node = promote(key);
return node ? node->value : -1;
}

void put(int key, int value) {
if (mCapacity == 0) return;

ListNode* node = promote(key);
if (node) {
node->value = value;
return;
} else {
if (freqTable.size() >= mCapacity) evictLast();
node = new ListNode(key, value);
BucketNode* bucket;
if (tail == NULL || tail->freq != 1) {
bucket = new BucketNode(1);
if (tail == NULL) {
} else {
bucket->prev = tail;
tail->next = bucket;
tail = bucket;
}
} else {
bucket = tail;
}
freqTable[key] = pair<BucketNode*, ListNode*>(bucket, node);
}
}

private:
inline ListNode* promote(int key) {
auto it = freqTable.find(key);
if (it == freqTable.end()) return NULL;
BucketNode* bucket = it->second.first;
ListNode* node = it->second.second;
bucket->removeOne(node);
BucketNode* newBucket;
if (bucket->prev == NULL || bucket->prev->freq != bucket->freq + 1) {
newBucket = new BucketNode(bucket->freq + 1);
if (bucket->prev == NULL) {
newBucket->next = bucket;
bucket->prev = newBucket;
} else {
bucket->prev->next = newBucket;
newBucket->prev = bucket->prev;
newBucket->next = bucket;
bucket->prev = newBucket;
}
} else {
newBucket = bucket->prev;
}

it->second.first = newBucket;
it->second.second = node;

if (bucket->empty()) removeBucket(bucket);

return node;
}

inline void removeBucket(BucketNode* bucket) {
if (bucket == head && bucket == tail) {
} else if (bucket == head) {
bucket->next->prev = NULL;
} else if (bucket == tail) {
bucket->prev->next = NULL;
tail = bucket->prev;
} else {
bucket->prev->next = bucket->next;
bucket->next->prev = bucket->prev;
}
delete bucket;
}

inline void evictLast() {
ListNode* node = tail->tail;
freqTable.erase(node->key);
tail->removeOne(node);
delete node;
if (tail->empty()) removeBucket(tail);
}

private:
int mCapacity;