Formatted question description: https://leetcode.ca/all/460.html

460. LFU Cache

Level

Hard

Description

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

  • get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
  • put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.

Follow up:

Could you do both operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Solution

Create two classes Node and DoublyLinkedList. Each object of Node has a key, a value, a frequency, the previous node and the next node. Each object of DoublyLinkedList has a size, a head and a tail.

In class LFUCache, maintain two maps cache and frequencyMap, which stores each key and the corresponding node, and stores each frequency and the corresponding doubly linked lists, respectively. Also maintain size, capacity and minCapacity.

For the constructor, initialize the two maps and the capacity.

For method get, get the node from cache. If the node exists, update the node’s frequency and return the node’s value. Otherwise, return -1.

For method put, check whether the node of the key already exists. If the node already exists, update the node’s value and update the node’s frequency. Otherwise, if size already reaches compacity, obtain the minimum frequency list using minFrequency and remove the last node, and decreasesize by 1. Then create a new node using key and value, update the maps, increase size by 1 and set minFrequency = 1.

Java

  • 
    public class LFU_Cache {
    
        public class LFUCache {
    
            // Save the key, value
            HashMap<Integer, Integer> vals;
    
            // Save the key to the value of the number of visits
            HashMap<Integer, Integer> counts;
    
            // 频率和一个里面所有key都是当前频率的list之间的映射
            HashMap<Integer, LinkedHashSet<Integer>> lists;
    
            int capacity;
    
            // Initialize the frequency of data occurrences
            int min = -1;
    
            public LFUCache(int cap) {
                capacity = cap;
                vals = new HashMap<>();
                counts = new HashMap<>();
                lists = new HashMap<>();
            }
    
            public int get(int key) {
                if (!vals.containsKey(key))
                    return -1;
    
                int count = counts.get(key);
                counts.put(key, count + 1);
                lists.get(count).remove(key);
    
                // Determine whether min should add 1
                if (count == min && lists.get(count).size() == 0) {
                    min++;
                }
    
                if (!lists.containsKey(count + 1)) {
                    lists.put(count + 1, new LinkedHashSet<>());
                }
    
                lists.get(count + 1).add(key);
                return vals.get(key);
            }
    
            public void put(int key, int value) {
                if (capacity <= 0)
                    return;
    
                if (vals.containsKey(key)) {
                    vals.put(key, value);
                    get(key);
                    return;
                }
    
                if (vals.size() >= capacity) {
                    int minFreKey = lists.get(min).iterator().next();
                    lists.get(min).remove(minFreKey);
                    vals.remove(minFreKey);
                    counts.remove(minFreKey);
                }
    
                vals.put(key, value);
                counts.put(key, 1);
                min = 1;
                if (!lists.containsKey(1)) {
                    lists.put(1, new LinkedHashSet<>());
                }
                lists.get(1).add(key);
            }
        }
    }
    
  • Todo
    
  • class List(object):
      @staticmethod
      def delete(elem):
        elem.prev.next = elem.next
        elem.next.prev = elem.prev
        elem.next = elem.prev = None
        return elem
    
      @staticmethod
      def move(elem, newPrev, newNext):
        elem.prev = newPrev
        elem.next = newNext
        newPrev.next = elem
        newNext.prev = elem
    
      @staticmethod
      def append(head, elem):
        List.move(elem, head.prev, head)
    
      @staticmethod
      def insertAfter(head, elem):
        List.move(elem, head, head.next)
    
      @staticmethod
      def isEmpty(head):
        return head.next == head.prev == head
    
      @staticmethod
      def initHead(head):
        head.prev = head.next = head
    
    
    class FreqNode(object):
      def __init__(self, freq):
        self.prev = self.next = None
        self.freq = freq
        self.head = Cache(-1, -1, self)
        List.initHead(self.head)
    
      def popCache(self):
        head = self.head
        ret = List.delete(head.next)
        if List.isEmpty(head):
          List.delete(self)
        return ret
    
    
    class Cache(object):
      def __init__(self, key, val, freqNode):
        self.prev = self.next = None
        self.freqNode = freqNode
        self.val = val
        self.key = key
    
      def increaseFreq(self):
        freqNode = self.freqNode
        newFreqNode = None
        if List.isEmpty(freqNode) or freqNode.next.freq != freqNode.freq + 1:
          newFreqNode = FreqNode(self.freqNode.freq + 1)
          List.insertAfter(freqNode, newFreqNode)
        else:
          newFreqNode = freqNode.next
        self.freqNode = newFreqNode
        List.delete(self)
        List.append(newFreqNode.head, self)
        if List.isEmpty(freqNode.head):
          List.delete(freqNode)
    
    
    class LFUCache(object):
      def __init__(self, capacity):
        self.d = {}
        self.cap = capacity
        self.head = FreqNode(-1)
        List.initHead(self.head)
    
      def get(self, key):
        if key not in self.d:
          return -1
        cacheNode = self.d[key]
        cacheNode.increaseFreq()
        return cacheNode.val
    
      def set(self, key, value):
        if self.cap == 0:
          return
        if key in self.d:
          cacheNode = self.d[key]
          cacheNode.val = value
          cacheNode.increaseFreq()
        else:
          if len(self.d) >= self.cap:
            del self.d[self.head.next.popCache().key]
          newFreqNode = FreqNode(0)
          newCacheNode = Cache(key, value, newFreqNode)
          List.append(newFreqNode.head, newCacheNode)
          List.insertAfter(self.head, newFreqNode)
          self.d[key] = newCacheNode
          newCacheNode.increaseFreq()
    
    # Your LFUCache object will be instantiated and called as such:
    # obj = LFUCache(capacity)
    # param_1 = obj.get(key)
    # obj.set(key,value)
    
    

Another one:

  • class LFUCache {
        Map<Integer, Node> cache;
        Map<Integer, DoublyLinkedList> frequencyMap;
        int size;
        int capacity;
        int minFrequency;
    
        public LFUCache(int capacity) {
            cache = new HashMap<Integer, Node>();
            frequencyMap = new HashMap<Integer, DoublyLinkedList>();
            this.capacity = capacity;
        }
        
        public int get(int key) {
            Node node = cache.get(key);
            if (node == null)
                return -1;
            else {
                increaseFrequency(node);
                return node.value;
            }
        }
        
        public void put(int key, int value) {
            if (capacity == 0)
                return;
            Node node = cache.get(key);
            if (node == null) {
                if (size == capacity) {
                    DoublyLinkedList minList = frequencyMap.get(minFrequency);
                    Node removeNode = minList.tail.prev;
                    cache.remove(removeNode.key);
                    minList.remove(removeNode);
                    size--;
                }
                Node newNode = new Node(key, value);
                cache.put(key, newNode);
                DoublyLinkedList list = frequencyMap.get(1);
                if (list == null) {
                    list = new DoublyLinkedList();
                    frequencyMap.put(1, list);
                }
                list.add(newNode);
                size++;
                minFrequency = 1;
            } else {
                node.value = value;
                increaseFrequency(node);
            }
        }
    
        private void increaseFrequency(Node node) {
            int frequency = node.frequency;
            DoublyLinkedList prevList = frequencyMap.get(frequency);
            prevList.remove(node);
            if (frequency == minFrequency && prevList.size == 0)
                minFrequency = frequency + 1;
            node.frequency++;
            DoublyLinkedList newList = frequencyMap.get(frequency + 1);
            if (newList == null) {
                newList = new DoublyLinkedList();
                frequencyMap.put(frequency + 1, newList);
            }
            newList.add(node);
        }
    }
    
    class Node {
        int key;
        int value;
        int frequency = 1;
        Node prev;
        Node next;
    
        public Node() {
            
        }
        
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    class DoublyLinkedList {
        int size;
        Node head;
        Node tail;
    
        public DoublyLinkedList() {
            size = 0;
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.prev = head;
        }
    
        public void remove(Node node) {
            size--;
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    
        public void add(Node node) {
            size++;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
            node.prev = head;
        }
    }
    
    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
    
  • Todo
    
  • class List(object):
      @staticmethod
      def delete(elem):
        elem.prev.next = elem.next
        elem.next.prev = elem.prev
        elem.next = elem.prev = None
        return elem
    
      @staticmethod
      def move(elem, newPrev, newNext):
        elem.prev = newPrev
        elem.next = newNext
        newPrev.next = elem
        newNext.prev = elem
    
      @staticmethod
      def append(head, elem):
        List.move(elem, head.prev, head)
    
      @staticmethod
      def insertAfter(head, elem):
        List.move(elem, head, head.next)
    
      @staticmethod
      def isEmpty(head):
        return head.next == head.prev == head
    
      @staticmethod
      def initHead(head):
        head.prev = head.next = head
    
    
    class FreqNode(object):
      def __init__(self, freq):
        self.prev = self.next = None
        self.freq = freq
        self.head = Cache(-1, -1, self)
        List.initHead(self.head)
    
      def popCache(self):
        head = self.head
        ret = List.delete(head.next)
        if List.isEmpty(head):
          List.delete(self)
        return ret
    
    
    class Cache(object):
      def __init__(self, key, val, freqNode):
        self.prev = self.next = None
        self.freqNode = freqNode
        self.val = val
        self.key = key
    
      def increaseFreq(self):
        freqNode = self.freqNode
        newFreqNode = None
        if List.isEmpty(freqNode) or freqNode.next.freq != freqNode.freq + 1:
          newFreqNode = FreqNode(self.freqNode.freq + 1)
          List.insertAfter(freqNode, newFreqNode)
        else:
          newFreqNode = freqNode.next
        self.freqNode = newFreqNode
        List.delete(self)
        List.append(newFreqNode.head, self)
        if List.isEmpty(freqNode.head):
          List.delete(freqNode)
    
    
    class LFUCache(object):
      def __init__(self, capacity):
        self.d = {}
        self.cap = capacity
        self.head = FreqNode(-1)
        List.initHead(self.head)
    
      def get(self, key):
        if key not in self.d:
          return -1
        cacheNode = self.d[key]
        cacheNode.increaseFreq()
        return cacheNode.val
    
      def set(self, key, value):
        if self.cap == 0:
          return
        if key in self.d:
          cacheNode = self.d[key]
          cacheNode.val = value
          cacheNode.increaseFreq()
        else:
          if len(self.d) >= self.cap:
            del self.d[self.head.next.popCache().key]
          newFreqNode = FreqNode(0)
          newCacheNode = Cache(key, value, newFreqNode)
          List.append(newFreqNode.head, newCacheNode)
          List.insertAfter(self.head, newFreqNode)
          self.d[key] = newCacheNode
          newCacheNode.increaseFreq()
    
    # Your LFUCache object will be instantiated and called as such:
    # obj = LFUCache(capacity)
    # param_1 = obj.get(key)
    # obj.set(key,value)
    
    

All Problems

All Solutions