Welcome to Subscribe On Youtube

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.

  • 
    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);
            }
        }
    }
    
    ############
    
    class LFUCache {
    
        private final Map<Integer, Node> map;
        private final Map<Integer, DoublyLinkedList> freqMap;
        private final int capacity;
        private int minFreq;
    
        public LFUCache(int capacity) {
            this.capacity = capacity;
            map = new HashMap<>(capacity, 1);
            freqMap = new HashMap<>();
        }
    
        public int get(int key) {
            if (capacity == 0) {
                return -1;
            }
            if (!map.containsKey(key)) {
                return -1;
            }
            Node node = map.get(key);
            incrFreq(node);
            return node.value;
        }
    
        public void put(int key, int value) {
            if (capacity == 0) {
                return;
            }
            if (map.containsKey(key)) {
                Node node = map.get(key);
                node.value = value;
                incrFreq(node);
                return;
            }
            if (map.size() == capacity) {
                DoublyLinkedList list = freqMap.get(minFreq);
                map.remove(list.removeLast().key);
            }
            Node node = new Node(key, value);
            addNode(node);
            map.put(key, node);
            minFreq = 1;
        }
    
        private void incrFreq(Node node) {
            int freq = node.freq;
            DoublyLinkedList list = freqMap.get(freq);
            list.remove(node);
            if (list.isEmpty()) {
                freqMap.remove(freq);
                if (freq == minFreq) {
                    minFreq++;
                }
            }
            node.freq++;
            addNode(node);
        }
    
        private void addNode(Node node) {
            int freq = node.freq;
            DoublyLinkedList list = freqMap.getOrDefault(freq, new DoublyLinkedList());
            list.addFirst(node);
            freqMap.put(freq, list);
        }
    
        private static class Node {
            int key;
            int value;
            int freq;
            Node prev;
            Node next;
    
            Node(int key, int value) {
                this.key = key;
                this.value = value;
                this.freq = 1;
            }
        }
    
        private static class DoublyLinkedList {
    
            private final Node head;
            private final Node tail;
    
            public DoublyLinkedList() {
                head = new Node(-1, -1);
                tail = new Node(-1, -1);
                head.next = tail;
                tail.prev = head;
            }
    
            public void addFirst(Node node) {
                node.prev = head;
                node.next = head.next;
                head.next.prev = node;
                head.next = node;
            }
    
            public Node remove(Node node) {
                node.next.prev = node.prev;
                node.prev.next = node.next;
                node.next = null;
                node.prev = null;
                return node;
            }
    
            public Node removeLast() {
                return remove(tail.prev);
            }
    
            public boolean isEmpty() {
                return head.next == tail;
            }
        }
    }
    
    
  • from collections import defaultdict
    
    class LFUCache:
        def __init__(self, capacity: int):
            self.capacity = capacity
            self.key_to_value = {}
            self.key_to_freq = defaultdict(int)
            self.freq_to_keys = defaultdict(OrderedDict)
            self.min_freq = 0
    
        def get(self, key: int) -> int:
            if key not in self.key_to_value:
                return -1
    
            # Update the frequency
            self._update_frequency(key)
            return self.key_to_value[key]
    
        def put(self, key: int, value: int) -> None:
            if self.capacity == 0:
                return
    
            if key in self.key_to_value:
                # Update the value and frequency
                self.key_to_value[key] = value
                self._update_frequency(key)
            else:
                if len(self.key_to_value) >= self.capacity:
                    # Evict the least frequently used key
                    self._evict()
    
                # Add the new key-value pair
                self.key_to_value[key] = value
                self.key_to_freq[key] = 1
                self.freq_to_keys[1][key] = None
                self.min_freq = 1
    
        def _update_frequency(self, key: int) -> None:
            freq = self.key_to_freq[key]
            del self.freq_to_keys[freq][key]
    
            if not self.freq_to_keys[freq]:
                # If there are no keys with the previous frequency, update min_freq
                if self.min_freq == freq:
                    self.min_freq += 1
                del self.freq_to_keys[freq]
    
            freq += 1
            self.key_to_freq[key] = freq
            self.freq_to_keys[freq][key] = None
    
        def _evict(self) -> None:
            keys = self.freq_to_keys[self.min_freq]
            evict_key, _ = keys.popitem(last=False)
            del self.key_to_value[evict_key]
            del self.key_to_freq[evict_key]
    
    # Your LFUCache object will be instantiated and called as such:
    # obj = LFUCache(capacity)
    # param_1 = obj.get(key)
    # obj.put(key,value)
    
    
    ##########
    
    class Node:
        def __init__(self, key: int, value: int) -> None:
            self.key = key
            self.value = value
            self.freq = 1
            self.prev = None
            self.next = None
    
    
    class DoublyLinkedList:
        def __init__(self) -> None:
            self.head = Node(-1, -1)
            self.tail = Node(-1, -1)
            self.head.next = self.tail
            self.tail.prev = self.head
    
        def add_first(self, node: Node) -> None:
            node.prev = self.head
            node.next = self.head.next
            self.head.next.prev = node
            self.head.next = node
    
        def remove(self, node: Node) -> Node:
            node.next.prev = node.prev
            node.prev.next = node.next
            node.next, node.prev = None, None
            return node
    
        def remove_last(self) -> Node:
            return self.remove(self.tail.prev)
    
        def is_empty(self) -> bool:
            return self.head.next == self.tail
    
    
    class LFUCache:
        def __init__(self, capacity: int):
            self.capacity = capacity
            self.min_freq = 0
            self.map = defaultdict(Node)
            self.freq_map = defaultdict(DoublyLinkedList)
    
        def get(self, key: int) -> int:
            if self.capacity == 0 or key not in self.map:
                return -1
            node = self.map[key]
            self.incr_freq(node)
            return node.value
    
        def put(self, key: int, value: int) -> None:
            if self.capacity == 0:
                return
            if key in self.map:
                node = self.map[key]
                node.value = value
                self.incr_freq(node)
                return
            if len(self.map) == self.capacity:
                ls = self.freq_map[self.min_freq]
                node = ls.remove_last()
                self.map.pop(node.key)
            node = Node(key, value)
            self.add_node(node)
            self.map[key] = node
            self.min_freq = 1
    
        def incr_freq(self, node: Node) -> None:
            freq = node.freq
            ls = self.freq_map[freq]
            ls.remove(node)
            if ls.is_empty():
                self.freq_map.pop(freq)
                if freq == self.min_freq:
                    self.min_freq += 1
            node.freq += 1
            self.add_node(node)
    
        def add_node(self, node: Node) -> None:
            freq = node.freq
            ls = self.freq_map[freq]
            ls.add_first(node)
            self.freq_map[freq] = ls
    
    
    # Your LFUCache object will be instantiated and called as such:
    # obj = LFUCache(capacity)
    # param_1 = obj.get(key)
    # obj.put(key,value)
    
    
    
  • type LFUCache struct {
    	cache    map[int]*node
    	freqMap  map[int]*list
    	minFreq  int
    	capacity int
    }
    
    func Constructor(capacity int) LFUCache {
    	return LFUCache{
    		cache:    make(map[int]*node),
    		freqMap:  make(map[int]*list),
    		capacity: capacity,
    	}
    }
    
    func (this *LFUCache) Get(key int) int {
    	if this.capacity == 0 {
    		return -1
    	}
    
    	n, ok := this.cache[key]
    	if !ok {
    		return -1
    	}
    
    	this.incrFreq(n)
    	return n.val
    }
    
    func (this *LFUCache) Put(key int, value int) {
    	if this.capacity == 0 {
    		return
    	}
    
    	n, ok := this.cache[key]
    	if ok {
    		n.val = value
    		this.incrFreq(n)
    		return
    	}
    
    	if len(this.cache) == this.capacity {
    		l := this.freqMap[this.minFreq]
    		delete(this.cache, l.removeBack().key)
    	}
    	n = &node{key: key, val: value, freq: 1}
    	this.addNode(n)
    	this.cache[key] = n
    	this.minFreq = 1
    }
    
    func (this *LFUCache) incrFreq(n *node) {
    	l := this.freqMap[n.freq]
    	l.remove(n)
    	if l.empty() {
    		delete(this.freqMap, n.freq)
    		if n.freq == this.minFreq {
    			this.minFreq++
    		}
    	}
    	n.freq++
    	this.addNode(n)
    }
    
    func (this *LFUCache) addNode(n *node) {
    	l, ok := this.freqMap[n.freq]
    	if !ok {
    		l = newList()
    		this.freqMap[n.freq] = l
    	}
    	l.pushFront(n)
    }
    
    type node struct {
    	key  int
    	val  int
    	freq int
    	prev *node
    	next *node
    }
    
    type list struct {
    	head *node
    	tail *node
    }
    
    func newList() *list {
    	head := new(node)
    	tail := new(node)
    	head.next = tail
    	tail.prev = head
    	return &list{
    		head: head,
    		tail: tail,
    	}
    }
    
    func (l *list) pushFront(n *node) {
    	n.prev = l.head
    	n.next = l.head.next
    	l.head.next.prev = n
    	l.head.next = n
    }
    
    func (l *list) remove(n *node) {
    	n.prev.next = n.next
    	n.next.prev = n.prev
    	n.next = nil
    	n.prev = nil
    }
    
    func (l *list) removeBack() *node {
    	n := l.tail.prev
    	l.remove(n)
    	return n
    }
    
    func (l *list) empty() bool {
    	return l.head.next == l.tail
    }
    
    
  • use std::cell::RefCell;
    use std::collections::HashMap;
    use std::rc::Rc;
    
    struct Node {
        key: i32,
        value: i32,
        freq: i32,
        prev: Option<Rc<RefCell<Node>>>,
        next: Option<Rc<RefCell<Node>>>,
    }
    
    impl Node {
        fn new(key: i32, value: i32) -> Self {
            Self {
                key,
                value,
                freq: 1,
                prev: None,
                next: None,
            }
        }
    }
    
    struct LinkedList {
        head: Option<Rc<RefCell<Node>>>,
        tail: Option<Rc<RefCell<Node>>>,
    }
    
    impl LinkedList {
        fn new() -> Self {
            Self {
                head: None,
                tail: None,
            }
        }
    
        fn push_front(&mut self, node: &Rc<RefCell<Node>>) {
            match self.head.take() {
                Some(head) => {
                    head.borrow_mut().prev = Some(Rc::clone(node));
                    node.borrow_mut().prev = None;
                    node.borrow_mut().next = Some(head);
                    self.head = Some(Rc::clone(node));
                }
                None => {
                    node.borrow_mut().prev = None;
                    node.borrow_mut().next = None;
                    self.head = Some(Rc::clone(node));
                    self.tail = Some(Rc::clone(node));
                }
            };
        }
    
        fn remove(&mut self, node: &Rc<RefCell<Node>>) {
            match (node.borrow().prev.as_ref(), node.borrow().next.as_ref()) {
                (None, None) => {
                    self.head = None;
                    self.tail = None;
                }
                (None, Some(next)) => {
                    self.head = Some(Rc::clone(next));
                    next.borrow_mut().prev = None;
                }
                (Some(prev), None) => {
                    self.tail = Some(Rc::clone(prev));
                    prev.borrow_mut().next = None;
                }
                (Some(prev), Some(next)) => {
                    next.borrow_mut().prev = Some(Rc::clone(prev));
                    prev.borrow_mut().next = Some(Rc::clone(next));
                }
            };
        }
    
        fn pop_back(&mut self) -> Option<Rc<RefCell<Node>>> {
            match self.tail.take() {
                Some(tail) => {
                    self.remove(&tail);
                    Some(tail)
                }
                None => None,
            }
        }
    
        fn is_empty(&self) -> bool {
            self.head.is_none()
        }
    }
    
    struct LFUCache {
        cache: HashMap<i32, Rc<RefCell<Node>>>,
        freq_map: HashMap<i32, LinkedList>,
        min_freq: i32,
        capacity: usize,
    }
    
    /**
     * `&self` means the method takes an immutable reference.
     * If you need a mutable reference, change it to `&mut self` instead.
     */
    impl LFUCache {
        fn new(capacity: i32) -> Self {
            Self {
                cache: HashMap::new(),
                freq_map: HashMap::new(),
                min_freq: 0,
                capacity: capacity as usize,
            }
        }
    
        fn get(&mut self, key: i32) -> i32 {
            if self.capacity == 0 {
                return -1;
            }
    
            match self.cache.get(&key) {
                Some(node) => {
                    let node = Rc::clone(node);
                    self.incr_freq(&node);
                    let value = node.borrow().value;
                    value
                }
                None => -1,
            }
        }
    
        fn put(&mut self, key: i32, value: i32) {
            if self.capacity == 0 {
                return;
            }
    
            match self.cache.get(&key) {
                Some(node) => {
                    let node = Rc::clone(node);
                    node.borrow_mut().value = value;
                    self.incr_freq(&node);
                }
                None => {
                    if self.cache.len() == self.capacity {
                        let list = self.freq_map.get_mut(&self.min_freq).unwrap();
                        self.cache.remove(&list.pop_back().unwrap().borrow().key);
                    }
                    let node = Rc::new(RefCell::new(Node::new(key, value)));
                    self.add_node(&node);
                    self.cache.insert(key, node);
                    self.min_freq = 1;
                }
            };
        }
    
        fn incr_freq(&mut self, node: &Rc<RefCell<Node>>) {
            let freq = node.borrow().freq;
            let list = self.freq_map.get_mut(&freq).unwrap();
            list.remove(node);
            if list.is_empty() {
                self.freq_map.remove(&freq);
                if freq == self.min_freq {
                    self.min_freq += 1;
                }
            }
            node.borrow_mut().freq += 1;
            self.add_node(node);
        }
    
        fn add_node(&mut self, node: &Rc<RefCell<Node>>) {
            let freq = node.borrow().freq;
            match self.freq_map.get_mut(&freq) {
                Some(list) => {
                    list.push_front(node);
                }
                None => {
                    let mut list = LinkedList::new();
                    list.push_front(node);
                    self.freq_map.insert(node.borrow().freq, list);
                }
            };
        }
    }
    
    /**
     * Your LFUCache object will be instantiated and called as such:
     * let obj = LFUCache::new(capacity);
     * let ret_1: i32 = obj.get(key);
     * obj.put(key, value);
     */
    
    
  • class Node {
    public:
        int key;
        int value;
        int freq;
        Node* prev;
        Node* next;
        Node(int key, int value) {
            this->key = key;
            this->value = value;
            this->freq = 1;
            this->prev = nullptr;
            this->next = nullptr;
        }
    };
    
    class DoublyLinkedList {
    public:
        Node* head;
        Node* tail;
        DoublyLinkedList() {
            this->head = new Node(-1, -1);
            this->tail = new Node(-1, -1);
            this->head->next = this->tail;
            this->tail->prev = this->head;
        }
        void addFirst(Node* node) {
            node->prev = this->head;
            node->next = this->head->next;
            this->head->next->prev = node;
            this->head->next = node;
        }
        Node* remove(Node* node) {
            node->next->prev = node->prev;
            node->prev->next = node->next;
            node->next = nullptr;
            node->prev = nullptr;
            return node;
        }
        Node* removeLast() {
            return remove(this->tail->prev);
        }
        bool isEmpty() {
            return this->head->next == this->tail;
        }
    };
    
    class LFUCache {
    public:
        LFUCache(int capacity) {
            this->capacity = capacity;
            this->minFreq = 0;
        }
    
        int get(int key) {
            if (capacity == 0 || map.find(key) == map.end()) {
                return -1;
            }
            Node* node = map[key];
            incrFreq(node);
            return node->value;
        }
    
        void put(int key, int value) {
            if (capacity == 0) {
                return;
            }
            if (map.find(key) != map.end()) {
                Node* node = map[key];
                node->value = value;
                incrFreq(node);
                return;
            }
            if (map.size() == capacity) {
                DoublyLinkedList* list = freqMap[minFreq];
                Node* node = list->removeLast();
                map.erase(node->key);
            }
            Node* node = new Node(key, value);
            addNode(node);
            map[key] = node;
            minFreq = 1;
        }
    
    private:
        int capacity;
        int minFreq;
        unordered_map<int, Node*> map;
        unordered_map<int, DoublyLinkedList*> freqMap;
    
        void incrFreq(Node* node) {
            int freq = node->freq;
            DoublyLinkedList* list = freqMap[freq];
            list->remove(node);
            if (list->isEmpty()) {
                freqMap.erase(freq);
                if (freq == minFreq) {
                    minFreq++;
                }
            }
            node->freq++;
            addNode(node);
        }
    
        void addNode(Node* node) {
            int freq = node->freq;
            if (freqMap.find(freq) == freqMap.end()) {
                freqMap[freq] = new DoublyLinkedList();
            }
            DoublyLinkedList* list = freqMap[freq];
            list->addFirst(node);
            freqMap[freq] = list;
        }
    };
    
    /**
     * 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);
     */
    

All Problems

All Solutions