LRU/LFU

146. LRU Cache

Design a cache includes 2 functions get(key) - Get the value 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 reached its capacity, it should invalidate the least recently used item before inserting a new item.

• get and put are O(1) operations

• Use doubleLinkedList and HashMap

• A removeNode and addToHead function

• A head and tail Node, the recent update note is next to head

class Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.hash = {}
        self.count = 0
        self.capacity = capacity
        self.head, self.tail = Node(), Node()
        
        self.head.next = self.tail
        self.tail.prev = self.head
    
    
    def moveToHead(self, node):
        node.next = self.head.next
        node.next.prev = node
        self.head.next = node
        node.prev= self.head
    
    
    def removeNode(self, node):
        node.next.prev = node.prev
        node.prev.next = node.next
    
    
    def get(self, key: int) -> int:
        if key not in self.hash: return -1
        node = self.hash[key]
        self.removeNode(node)
        self.moveToHead(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.hash:
            node = self.hash[key]
            node.val = value
            self.removeNode(node)
            self.moveToHead(node)
        else:
            node = Node(key, value)
            self.hash[key] = node
            self.moveToHead(node)
            self.count +=1
            if self.count > self.capacity:
                self.hash.pop(self.tail.prev.key)
                self.removeNode(self.tail.prev)
                self.count -= 1

460. LFU Cache

Design a data structure supports 2 functions get(key) - Get the value 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

• get and put are O(1) operations

• 3 hashMap

  1. values

  2. counts

  3. countToKey>

// cornor case: capacity <= 0

class LFUCache {
    // all hashtables, support O(1) add and delete
    // key: value
    Map<Integer, Integer> values;
    // key: count
    Map<Integer, Integer> counts;
    // count: [keys]
    Map<Integer, LinkedHashSet<Integer>> countToSet;
    int min, capacity;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        min = 0;
        values = new HashMap<>();
        counts = new HashMap<>();
        countToSet = new HashMap<>();
        countToSet.put(1, new LinkedHashSet<Integer>());
    }

    public int get(int key) {
        if(!values.containsKey(key)) return -1;
        int count = counts.get(key);
        // update counts
        counts.put(key, count+1);
        // updates countToSet
        countToSet.get(count).remove(key);
        if(min == count && countToSet.get(count).size() == 0){
           min = count+1; 
        }
        if(!countToSet.containsKey(count+1)){
            countToSet.put(count+1, new LinkedHashSet<Integer>());
        }
        countToSet.get(count+1).add(key);

        return values.get(key);
    }

    public void put(int key, int value) {
        if(capacity <= 0) return;
        if(values.containsKey(key)){
            values.put(key, value);
            // update counts and countToSet
            get(key);
        }else{
            // 必須先做update的動作, 不然會包含剛更新的資訊
            if(values.size() == capacity){
                int k = countToSet.get(min).iterator().next();
                values.remove(k);
                counts.remove(k);
                countToSet.get(min).remove(k);
            }

            min = 1;
            values.put(key, value);
            counts.put(key, 1);
            countToSet.get(1).add(key);
        }
    }
}

• Use DoubleLinkedList and 2 HashMap (see description)

  1. NodeMap<key, Node>

  2. FreqMap<freq, doublelLinkedList>

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.freq = 1
        self.prev = None
        self.next = None
        

class DLinkedList:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.size = 0
        self.head.next = self.tail
        self.tail.prev = self.head
        
        
    def removeNode(self, node):
        node.next.prev = node.prev
        node.prev.next = node.next
        self.size -= 1
        
    
    def appendNode(self, node):
        node.next = self.head.next
        node.next.prev = node
        self.head.next = node
        node.prev = self.head
        self.size += 1
        

class LFUCache:

    def __init__(self, capacity: int):
        self.nodeMap = {}
        self.freqMap = collections.defaultdict(DLinkedList)
        self.capacity = capacity
        self.count = 0
        self.minFreq = 1
        

    def get(self, key: int) -> int:
        if key not in self.nodeMap: return -1
        node = self.nodeMap[key]
        freq = node.freq
        self.freqMap[freq].removeNode(node)
        if self.freqMap[freq].size == 0 and self.minFreq == freq:
            self.minFreq = freq + 1
        self.freqMap[freq+1].appendNode(node)
        node.freq += 1
        return node.value
        

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0: return
        
        if key in self.nodeMap:
            self.nodeMap[key].value = value
            self.get(key)
        else:
            if self.count == self.capacity:
                DList = self.freqMap[self.minFreq]
                self.nodeMap.pop(DList.tail.prev.key)
                DList.removeNode(DList.tail.prev)
                self.count -= 1
                
            node = Node(key, value)
            self.nodeMap[key] = node
            self.freqMap[1].appendNode(node)
            self.minFreq = 1
            self.count += 1