Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:


	LFUCache(int capacity) Initializes the object with the capacity of the data structure.
	int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
	void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.


To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.

The functions&nbsp;get&nbsp;and&nbsp;put&nbsp;must each run in O(1) average time complexity.

&nbsp;
Example 1:

Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Explanation
// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is  most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // return 1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
&nbsp;                // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // return 4
                 // cache=[4,3], cnt(4)=2, cnt(3)=3


&nbsp;
Constraints:


	0 &lt;= capacity&nbsp;&lt;= 104
	0 &lt;= key &lt;= 105
	0 &lt;= value &lt;= 109
	At most 2 * 105&nbsp;calls will be made to get and put.


&nbsp;
&nbsp;
class Node:
    
    def __init__(self, key, val, cnt=1, nxxt=None, prev=None):
        self.key = key
        self.val = val
        self.cnt = cnt
        self.nxxt = nxxt
        self.prev = prev
        
        
class NodeList(Node):
    
    def __init__(self):
        self.head = Node(0,0)
        self.tail = Node(0,0)
        self.head.nxxt = self.tail
        self.tail.prev = self.head
        self.size = 0
        
        
    def addFront(self, node):
        temp = self.head.nxxt
        self.head.nxxt = node
        node.prev = self.head
        node.nxxt = temp
        temp.prev = node
        
        self.size += 1
        
        
    def removeNode(self, node):
        delprev = node.prev
        delnxxt = node.nxxt
        delprev.nxxt = delnxxt
        delnxxt.prev = delprev
        
        self.size -= 1
        

class LFUCache(NodeList):

    def __init__(self, capacity: int):
        self.keyNode = {}
        self.freqNodeList = {}
        self.maxSizeCache = capacity
        self.currSize = 0
        self.minFreq = 0
        
        
    def updateFreqNodeList(self, node):
        del self.keyNode[node.key]
        nodelist = self.freqNodeList[node.cnt]
        nodelist.removeNode(node)
        
        if node.cnt == self.minFreq and self.freqNodeList[node.cnt].size == 0:
            self.minFreq += 1
            
        if (node.cnt+1) in self.freqNodeList:
            nextHigherFreqNodeList = self.freqNodeList[node.cnt+1]
        else:
            nextHigherFreqNodeList = NodeList()
            
        node.cnt += 1
        nextHigherFreqNodeList.addFront(node)
        
        self.freqNodeList[node.cnt] = nextHigherFreqNodeList
        self.keyNode[node.key] = node
        

    def get(self, key: int) -> int:
        if key in self.keyNode:
            node = self.keyNode[key]
            ans = node.val
            self.updateFreqNodeList(node)
            
            return ans
        
        else:
            return -1
        

    def put(self, key: int, value: int) -> None:
        if self.maxSizeCache == 0:
            return
        
        if key in self.keyNode:
            node = self.keyNode[key]
            node.val = value
            self.updateFreqNodeList(node)
            return
        
        else:
            if self.currSize == self.maxSizeCache:
                nodelist = self.freqNodeList[self.minFreq]
                del self.keyNode[nodelist.tail.prev.key]
                nodelist.removeNode(nodelist.tail.prev)
                self.currSize -= 1
                
            self.currSize += 1
            self.minFreq = 1
            
            if self.minFreq in self.freqNodeList:
                nodelist = self.freqNodeList[self.minFreq]
            else:
                nodelist = NodeList()
                
            node = Node(key, value)
            nodelist.addFront(node)
            
            self.keyNode[key] = node
            self.freqNodeList[self.minFreq] = nodelist
        


# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
	class LFUCache {
    // Declare Node class for Doubly Linked List 
    class Node{
        int key,value,freq;// to store key,value and frequency
        Node prev,next;// Next and Previous Pointers
        Node(int k,int v){
        // initializing in constructor
            key=k;
            value=v;
            freq=1;
        }
        
    }
    // Declare class for List of Doubly Linked List
    class List{
        int size;
        Node head,tail;
        List(){
        // initializing in constructor
            size=0;
            head=new Node(-1,-1);// Default values
            tail=new Node(-1,-1);
            head.next=tail;
            tail.prev=head;
        }
        // To insert at the start of the list
        void ins(Node newNode){
            Node temp=head.next;
            head.next=newNode;
            newNode.prev=head;
            newNode.next=temp;
            temp.prev=newNode;
            size++;
            
        }
        // To delete specific node
        void del(Node newNode){
            Node pr=newNode.prev;
            Node nx=newNode.next;
            pr.next=nx;
            nx.prev=pr;
            size--;
        }
    }
    Map<Integer,Node>mp;// to store key and Node
    Map<Integer,List>listMap;// to store frequency and Doubly Linked List
    int maxSize,minFreq,currSize;// to store total size , minimum frequency and current size of the list
    public LFUCache(int capacity) {
        // initializing in constructor
        maxSize=capacity;
        minFreq=0;
        currSize=0;
        mp=new HashMap<Integer,Node>();
        listMap=new HashMap<Integer,List>();
    }
    
    public int get(int key) {
        // if map contains the specific key 
        if(mp.containsKey(key)){
            Node node=mp.get(key);
            int val=node.value;
            updateFreq(node);// to update the frequency of the node
            return val;            
        }
        //otherwise
        return -1;
    }
    
    public void put(int key, int value) {
        // one of the corner case
        if(maxSize==0)
            return;
        // if map contains the specific key 
        if(mp.containsKey(key)){
            Node node=mp.get(key);
            node.value=value; // update the value of the node
            updateFreq(node);// to update the frequency of the node
        }
        else{
        // if current size is equal to spcified capacity of the LFU list
            if(maxSize==currSize){
                List list=listMap.get(minFreq);
                mp.remove(list.tail.prev.key);// to remove the LRU of the LFU from key-node map
                
                // here LFU is list and even if its is a single element or multiple tail.prev(LRU) is the required element
                
                list.del(list.tail.prev);// to remove the LRU of the LFU from freq-list map
                currSize--;
            }
            currSize++;
            minFreq=1;// reset minFreq to 1 because of adding new node
            List list= new List();
            // If listMap already contains minFreq list
            if(listMap.containsKey(minFreq)){
                list=listMap.get(minFreq);
            }
            Node node = new Node(key,value);// creating a new node
            list.ins(node); // inserting new node to the list
            mp.remove(key); 
            mp.put(key,node); // inserting updated new node to the key-node map
            listMap.remove(minFreq);
            listMap.put(minFreq,list);// inserting updated list to the listMap        
        }
    }
    public void updateFreq(Node newNode){
        mp.remove(newNode.key);// to remove the node from key-node map
        listMap.get(newNode.freq).del(newNode);// to remove the node from listmap
        
        // If node's freq was minimum and after removing it from the listMap, size is 0
        if(newNode.freq==minFreq && listMap.get(newNode.freq).size==0){
            minFreq++;
        }
        List higherFreqList= new List();
        // If listMap already contains node's freq +1 th list
        if(listMap.containsKey(newNode.freq+1)){
            higherFreqList= listMap.get(newNode.freq+1);
        }
        newNode.freq++; // updating node's frequency
        higherFreqList.ins(newNode); // inserting node to list
        listMap.remove(newNode.freq);
        listMap.put(newNode.freq,higherFreqList);// reinserting list to listMap
        mp.remove(newNode.key);
        mp.put(newNode.key,newNode);// reinserting node to key-node map
    }
}
class list_node {
public:
    int key, val, cnt;
    list_node* next;
    list_node* prev;
    list_node(int k, int v, list_node* n, list_node* p) {
        key = k; val = v; cnt = 1;
        next = n; prev = p;
    }
};
class LFUCache {
public:
    int min_cnt;
    bool zero;
    unordered_map<int, list_node*> key2node;
    unordered_map<int, pair<list_node*, list_node*>> cnt2list;
    LFUCache(int capacity) {
        cin.tie(0); ios_base::sync_with_stdio(0);
        min_cnt = 0;
        c = capacity;
        zero = (c == 0);
    }
    
    int get(int key) {
        if(zero) return -1;
        auto it = key2node.find(key);
        if(it == key2node.end() || it->second == NULL) return -1;
        addcnt(key);
        return it->second->val;
    }
    
    void put(int key, int value) {
        if(zero) return;
        auto it = key2node.find(key);
        if(it != key2node.end() && it->second != NULL) {
            addcnt(key);
            it->second->val = value;
            return;
        }
        if(c) --c;
        else {
            key2node[cnt2list[min_cnt].first->key] = NULL;
            list_node* tmp = cnt2list[min_cnt].first;
            if(tmp->next) tmp->next->prev = NULL;
            cnt2list[min_cnt].first = tmp->next;
            if(cnt2list[min_cnt].second == tmp) cnt2list[min_cnt].second = NULL; 
        }

        min_cnt = 1;
        list_node* node = new list_node(key, value, NULL, NULL);
        key2node[key] = node;
        if(cnt2list.find(1) == cnt2list.end() || cnt2list[1].first == NULL) {
            cnt2list[1].first = cnt2list[1].second = node;
        }
        else {
            node->prev = cnt2list[1].second;
            cnt2list[1].second->next = node;
            cnt2list[1].second = node;
        }
    }
private:
    int c;
    void addcnt(int key) {
        if(cnt2list[key2node[key]->cnt].first == key2node[key]) 
            cnt2list[key2node[key]->cnt].first = key2node[key]->next;
        if(cnt2list[key2node[key]->cnt].second == key2node[key]) 
            cnt2list[key2node[key]->cnt].second = key2node[key]->prev;
        if(min_cnt == key2node[key]->cnt && cnt2list[key2node[key]->cnt].first == NULL) min_cnt++;
        key2node[key]->cnt++;
        if(key2node[key]->prev) key2node[key]->prev->next = key2node[key]->next;
        if(key2node[key]->next) key2node[key]->next->prev = key2node[key]->prev;
        key2node[key]->next = NULL;
        auto lit = cnt2list.find(key2node[key]->cnt);
        if(lit == cnt2list.end() || lit->second.first == NULL) {
            cnt2list[key2node[key]->cnt].first = cnt2list[key2node[key]->cnt].second = key2node[key];
            key2node[key]->prev = NULL;
        }
        else {
            key2node[key]->prev = cnt2list[key2node[key]->cnt].second;
            cnt2list[key2node[key]->cnt].second->next = key2node[key];
            cnt2list[key2node[key]->cnt].second = key2node[key];
        }
    }
};
/**
 * @param {number} capacity
 */
var LFUCache = function(capacity) {
    this.capacity = capacity;
    this.cache = [];
};

/** 
 * @param {number} key
 * @return {number}
 */
LFUCache.prototype.get = function(key) {
    let val = -1;
    if (!this.capacity) return val;
    const existIndex = this.cache.findIndex(item => item.key === key);
    if (existIndex > -1) {
        const item = this.cache[existIndex];
        val = item.value;
        item.count++;
        this.cache.splice(existIndex, 1);
        this.cache.unshift(item);
    }
    return val;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LFUCache.prototype.put = function(key, value) {
    if (!this.capacity) return;
    const existIndex = this.cache.findIndex(item => item.key === key);
    if (existIndex > -1) {
        // new item already exists，rewrite the value and increase count
        const existItem = this.cache[existIndex];
        existItem.value = value;
        existItem.count++;
        this.cache.splice(existIndex, 1);
        this.cache.unshift(existItem);
    } else {
        // new item doesn't exist
        if (this.cache.length === this.capacity) {
            // reach the capacity, need to clear LFU
            let lfuIndex = 0;
            let leastCount = this.cache[lfuIndex].count;
            for (let i = 1; i < this.cache.length; i++) {
                const item = this.cache[i];
                if (item.count <= leastCount) {
                    leastCount = item.count;
                    lfuIndex = i;
                }
            }
            this.cache.splice(lfuIndex, 1);
            // after clear LFU, push the new item
            this.cache.unshift({
                key,
                value,
                count: 1
            });
        } else {
            // new item can be pushed
            this.cache.unshift({
                key,
                value,
                count: 1
            });
        }
    }
};

/** 
 * Your LFUCache object will be instantiated and called as such:
 * var obj = new LFUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */
LFU Cache