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


  • 1
    C

    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* head;
            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) {
                    tail = head = NULL;
                } else if (node == head) {
                    node->next->prev = NULL;
                    head = node->next;
                } 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;
            }
            
            void addOne(ListNode* node) {
                if (head == NULL) {
                    head = tail = node;
                } else {
                    head->prev = node;
                    node->next = head;
                    head = node;
                }
            }
            
            bool empty() { return head == NULL; }
        };
        
    public:
        LFUCache(int capacity) : mCapacity(capacity) {
            head = tail = NULL;
        }
        
        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);
                    bucket->addOne(node);
                    if (tail == NULL) {
                        head = tail = bucket;
                    } else {
                        bucket->prev = tail;
                        tail->next = bucket;
                        tail = bucket;
                    }
                } else {
                    bucket = tail;
                    bucket->addOne(node);
                }
                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);
                newBucket->addOne(node);
                if (bucket->prev == NULL) {
                    head = newBucket;
                    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;
                newBucket->addOne(node);
            }
            
            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) {
                head = tail = NULL;
            } else if (bucket == head) {
                bucket->next->prev = NULL;
                head = bucket->next;
            } 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;
        BucketNode* head;
        BucketNode* tail;
        unordered_map<int, pair<BucketNode*, ListNode*>> freqTable;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.