> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/simulation/lrulfu.md).

# 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

```python
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>

```java
// 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](https://leetcode.com/problems/lfu-cache/discuss/207673/Python-concise-solution-**detailed**-explanation%3A-Two-dict-%2B-Doubly-linked-list))
  1. NodeMap\<key, Node>
  2. FreqMap\<freq, doublelLinkedList>

```python
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
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/simulation/lrulfu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.