C++ double linked list and HashMap O(1)


  • 0
    B

    I use two sets of pointers to maintain the frequency relation between nodes.
    I put the nodes with same frequency in a linked list, from head to tail, they are new to old.
    Then I connect the head of all linked list, from head to tail, they are high freq to low freq.

    for all linked lists, I have dummy head and tail so the implementation can be simpler.

    In the Node struct, I have freq data member, which can be used to find the head of current freq linked list. I have key data member, which can be used to find the node.

    I used three HashMap. heads is all dummy head of active frequency. tail is all dummy tail of active frequency. cache is all active nodes.

    The algorithm is:
    get:

    • used key to find the node from cache, then remove it from current frequency list, and finally insert it to the head of next frequency list.
    • when remove node from a list, we check if the list is empty, if yes, we remove the list
    • when insert node to a list, we check if the list of corresponding frequency is exist, if no, we create one.

    set:

    • if the key already exist, we update the value, and call get to update node location
    • if cache has free space, we create new node and insert the node to the list of frequency = 1
    • if cache does not have free space, we find the node to evict, which is the node before the tail node of list before ftail. We then remove the node and move the node to the list of frequency = 1, when we do remove and insert, we need to check if list is empty and the destination list is exist.

    Overall, the code is ugly with repeated code, it can be improved by having some functions to represent the repeated code. On the other hand, it is still easy to read and understand. And it is fast as 82%.

    class LFUCache {
    public:
        struct Node
        {
            int freq;
            int key;
            int val;
            Node * prev;
            Node * next;
            Node * fprev;
            Node * fnext;
            Node(int f, int k, int v)
            {
                freq = f;
                key = k;
                val = v;
                prev = NULL;
                next = NULL;
                fprev = NULL;
                fnext = NULL;
            };
        };
        int cap;
        Node * fhead;
        Node * ftail;
        unordered_map<int,Node*>cache;
        unordered_map<int,Node*>heads;
        unordered_map<int,Node*>tails;
        
        LFUCache(int capacity) {
            cap = capacity;
            fhead = new Node(0,0,0);
            ftail = new Node(0,0,0);
            fhead -> fnext = ftail;
            ftail -> fprev = fhead;
        }
        
        int get(int key) {
            if(cache.find(key)==cache.end()) return -1;
            auto node = cache[key];
            int freq = node -> freq;
            if(heads.find(freq+1)==heads.end())
            {
                auto head = new Node(freq+1,0,0);
                auto tail = new Node(freq+1,0,0);
                head -> next = tail;
                tail -> prev = head;
                head -> fnext = heads[freq];
                head -> fprev = heads[freq] -> fprev;
                heads[freq] -> fprev -> fnext = head;
                heads[freq] -> fprev = head;
                heads[freq+1] = head;
                tails[freq+1] = tail;
            }
            
            node -> prev -> next = node -> next;
            node -> next -> prev = node -> prev;
            //if current freq is empty, remove head
            if(heads[node->freq] -> next == tails[node->freq])
            {
                heads[node->freq] -> fprev -> fnext = heads[node->freq] -> fnext;
                heads[node->freq] -> fnext -> fprev = heads[node->freq] -> fprev;
                heads.erase(node->freq);
                tails.erase(node->freq);
            }
            node -> freq += 1;
            auto head = heads[node->freq];
            node -> next = head -> next;
            node -> prev = head;
            head -> next -> prev = node;
            head -> next = node;
            return node -> val;
        }
        
        void set(int key, int value) {
            if(cap == 0 && fhead -> fnext == ftail) return;
    
            if(cache.find(key)!=cache.end())
            {
                cache[key]->val = value;
                get(key);
                return;
            }
            if(cap > 0)
            {
                cap -= 1;
                auto node = new Node(1,key,value);
                if(heads.find(1)==heads.end())
                {
                    auto head = new Node(1,0,0);
                    auto tail = new Node(1,0,0);
                    head -> next = tail;
                    tail -> prev = head;
                    head -> fnext = ftail;
                    head -> fprev = ftail -> fprev;
                    ftail -> fprev -> fnext = head;
                    ftail -> fprev = head;
                    heads[1] = head;
                    tails[1] = tail;
                }
                auto head = heads[1];
                node -> next = head -> next;
                node -> prev = head;
                head -> next -> prev = node;
                head -> next = node;
                cache[key] = node;
                return;
            }
            auto node = tails[ftail -> fprev -> freq] -> prev;
            node -> prev -> next = node -> next;
            node -> next -> prev = node -> prev;
            //if current freq is empty, remove head
            if(heads[node->freq] -> next == tails[node->freq])
            {
                heads[node->freq] -> fprev -> fnext = heads[node->freq] -> fnext;
                heads[node->freq] -> fnext -> fprev = heads[node->freq] -> fprev;
                heads.erase(node->freq);
                tails.erase(node->freq);
            }
            cache.erase(node->key);
            node -> freq = 1;
            node -> key = key;
            node -> val = value;
            
            if(heads.find(1)==heads.end())
            {
                auto head = new Node(1,0,0);
                auto tail = new Node(1,0,0);
                head -> next = tail;
                tail -> prev = head;
                head -> fnext = ftail;
                head -> fprev = ftail -> fprev;
                ftail -> fprev -> fnext = head;
                ftail -> fprev = head;
                heads[1] = head;
                tails[1] = tail;
            }
            auto head = heads[1];
            node -> next = head -> next;
            node -> prev = head;
            head -> next -> prev = node;
            head -> next = node;
            cache[key] = node;
            return;
        }
    };
    
    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.set(key,value);
     */

Log in to reply
 

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