LeetCode 460 LFU Cache

LeetCode

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 get and put must each run in O(1) average time complexity.

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.
                 // 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=[3,4], cnt(4)=2, cnt(3)=3

Constraints: 0 <= capacity <= 10<sup>4</sup>
0 <= key <= 10<sup>5</sup> 0 <= value <= 10<sup>9</sup>
At most `2 10<sup>5</sup>calls will be made togetandput`.

双Map+分区LL解题思路(推荐)：

类似于LRU，但本质上区别较大。一开始思路可参考算法II，它的缺点是move_up需要从该层的某个位置删除加入到上一个freq较大的下一层的末尾。为了避免此问题，考虑不用单一链表，而是对应不同freq的多个链表。所以引入freq_map来记录每个LL的起点。由于每个LL都是从旧到新（跟LRU一样），新的插入到末尾，删除的从头删除，所以需要是循环链表，最终是一个循环双向LL。ListNode的next和prev都指向自己

move_up解决了，另一个难点是get_lfu_node，这里引入min_freq来记录当前最小的freq。它的更新由三方面引起:新节点min_freq=1，get的move_up和旧节点move_up。后两者是一样的，都是move_up后查看min_freq所以的LL是否为空。

总结一下与LRU的区别：

• set也是三种情况但要更新min_freq
• ListNode多了freq，next prev指向自己形成循环LL，key，val含默认值
• Cache中多了freq map和min_freq
• 链表操作为move_up和get_lru_node，这点和算法II一样
• 节点操作为remove_node, add_to_tail和LRU一样。add_to_tail是分层LL末尾不是总链表末尾

注意事项：

1. 用了一小时debug min_freq的更新，move_up发生时候，检查min_freq所在的LL，若为空，增加1，而不是检查node_freq所在的LL。新节点令min_freq变成1
2. 思路上：LRU是Map to Node in 全局双向LL，而LRU是Map to Node in 分区双向循环LL。存在多条LL，每个LL的起点终点存在freq map中。min_freq记录要删除的LFU节点对应的频率。
3. 思路上：再LRU基础上增加freq域默认为1，key, val默认为0，prev和next指向自己，形成双向循环LL
4. capacity可能为0，LRU那天capacity大于0
5. 双向LL加入新节点有两个赋值语句，不要忘记node.prev, node.next = predecessor, successor

Python代码：

class LFUCache(TestCases):

    def __init__(self, capacity: int):
        self.key_to_node = collections.defaultdict(ListNode)
        self.freq_to_head = collections.defaultdict(ListNode)
        self.min_freq = 1
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node_freq = node.freq
            self.move_up(node)
            # if self.freq_to_head[node_freq].next == self.freq_to_head[node_freq]:
              #  self.min_freq = node.freq
            if self.freq_to_head[self.min_freq].next == self.freq_to_head[self.min_freq]:
                self.min_freq += 1
            return node.val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node.val = value
            self.move_up(node)
            if self.freq_to_head[self.min_freq].next == self.freq_to_head[self.min_freq]:
                self.min_freq += 1
        elif self.capacity > 0:
            if len(self.key_to_node) == self.capacity:
                lru_node = self.get_lru_node()
                self.key_to_node.pop(lru_node.key)
                self.remove_node(lru_node)
            new_node = ListNode(key, value)
            self.add_to_tail(new_node)
            self.key_to_node[key] = new_node
            self.min_freq = 1

    def move_up(self, node):
        self.remove_node(node)
        node.freq += 1
        self.add_to_tail(node)

    def get_lru_node(self):
        head = self.freq_to_head[self.min_freq]
        return head.next

    def add_to_tail(self, node):
        head = self.freq_to_head[node.freq]
        predecessor, successor = head.prev, head
        predecessor.next, successor.prev = node, node
        node.prev, node.next = predecessor, successor

    def remove_node(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None

class ListNode:

    def __init__(self, key=0, val=0, freq=1):
        self.key = key
        self.val = val
        self.freq = freq
        self.prev = self # self-pointed
        self.next = self

算法分析：

Insert时间复杂度为O(1)，空间复杂度O(n)

---

类LRU算法II解题思路(不推荐)：

似乎Leetcode改变了要求，之前此法是可以通过的，但现在put要求O(1)了，所以TLE了。

注意事项：

1. 再LRU基础上增加freq域默认为1，新节点插入doubly LL末尾，LL以freq从大到小，同一个频率从最旧到最新(LRU)。所以若满容量要删除节点从freq=1中往前找到该层的首节点
2. capacity可能为0，LRU那天capacity大于0
3. move_up是往前搜索, it = it.prev而不是用next。比较条件为it.freq < node.freq，加入到同一频率的末尾
4. 双向LL加入新节点有两个赋值语句，不要忘记node.prev, node.next = predecessor, successor

Python代码：

class LFUCache(TestCases):

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.key_to_node = collections.defaultdict(ListNode)
        # newly inserted to tail
        self.head, self.tail = ListNode(0, 0), ListNode(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

    def get(self, key: int) -> int:
        if key in self.key_to_node:
            self.move_up(self.key_to_node[key])
            return self.key_to_node[key].val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.key_to_node:
            self.key_to_node[key].val = value
            self.move_up(self.key_to_node[key])
        elif self.capacity > 0: # remember
            if len(self.key_to_node) == self.capacity:
                node = self.get_lfu_node()
                self.key_to_node.pop(node.key)
                self.remove(node)
            new_node = ListNode(key, value)
            self.add_to_tail(new_node)
            self.key_to_node[key] = new_node

    def get_lfu_node(self):
        it = self.tail.prev
        min_freq = it.freq
        while it != self.head and it.freq == min_freq:
            it = it.prev # remember prev not next
        return it.next

    def move_up(self, node):
        node.freq += 1
        it = node.prev
        self.remove(node)
        while it != self.head and it.freq < node.freq: # remember <=
            it = it.prev # remember prev not next
        predecessor, successor = it, it.next
        predecessor.next, successor.prev = node, node
        node.prev, node.next = predecessor, successor

    def add_to_tail(self, node):
        predecessor, successor = self.tail.prev, self.tail
        predecessor.next, successor.prev = node, node
        node.prev, node.next = predecessor, successor # remember

    def remove(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None


class ListNode:

    def __init__(self, key, val, freq=1, prev=None, next=None):
        self.key = key
        self.val = val
        self.freq = freq
        self.prev = prev
        self.next = next

注意事项：

1. 在LRU基础上，ListNode引入freq域， 当频率增加时候，找到新的频率对应的末节点插入。其它基本不变。插入最差是O(n). 要提高的话，需要加入map和minFreq来迅速定位下一个插入位置。第一个Map不变，但LL不再是一串，而是按频率大小的多串。

Java代码：

Map<Integer, ListNode> map;
ListNode head; // from most frequent to less
ListNode tail;
int capacity;
public L460LFUCache(int capacity) {
	this.capacity = capacity;
	head = new ListNode(-1, -1, Integer.MAX_VALUE);
	tail = new ListNode(-1, -1, Integer.MIN_VALUE);
	head.next = tail;
	tail.prev = head;
	map = new HashMap<>();
}

public int get(int key) {
	if(!map.containsKey(key))
		return -1;
	moveUp(key);
	return map.get(key).val;
}

public void put(int key, int value) {
	if(capacity == 0)
		return;
	
	if(map.containsKey(key)) {
		moveUp(key);
		map.get(key).val = value; // remember to update the value
	}
	else {
		if(map.size() == capacity) {
			map.remove(tail.prev.key);
			deleteNode(tail.prev);
		}
		// add new key
		ListNode newNode = new ListNode(key, value);
		addNode(newNode, tail);
		map.put(key, newNode);
		moveUp(key);
	}
}

void moveUp(int key) {
	ListNode curNode = map.get(key);
	curNode.addOne();
	ListNode iterNode = curNode;
	while(iterNode.freq <= curNode.freq)
		iterNode = iterNode.prev;
	if(iterNode != curNode) {
		deleteNode(curNode);
		addNode(curNode, iterNode.next);
	}
}

void addNode(ListNode curNode, ListNode nextNode) {
	ListNode prevNode = nextNode.prev;
	prevNode.next = curNode;
	curNode.prev = prevNode;
	curNode.next = nextNode;
	nextNode.prev = curNode;
}
// delete head node and updated node
void deleteNode(ListNode curNode) {
	ListNode nextNode = curNode.next;
	ListNode prevNode = curNode.prev;
	prevNode.next = nextNode;
	nextNode.prev = prevNode;
	curNode.next = null;
	curNode.prev = null;
}

public class ListNode {
	public int key;
	public int val;
	public int freq = 1;
	public ListNode next;
	public ListNode prev;

	public ListNode(int key, int val) {
		this.key = key;
		this.val = val;
	}
	
	public ListNode(int key, int val, int freq) {
		this.key = key;
		this.val = val;
		this.freq = freq;
	}
	
	public void addOne() {
		freq++;
	}
}

算法分析：

Insert时间复杂度为O(n)，空间复杂度O(k)