Problem statement

https://leetcode.com/problems/lfu-cache/

Solution

[code and explanation is borrowed from https://leetcode.com/problems/lfu-cache/discuss/207673/Python-concise-solution-**detailed**-explanation%3A-Two-dict-%2B-Doubly-linked-list]

Let us use circled double linked list, that is where last elements points to the first. Also we use dummy node to deal with edge cases. For our doubly linked list we can:

  1. append(node): append the node to the head of the linked list.
  2. pop(node = None): remove the referenced node. If None is given, remove the one from tail, which is the least recently used.

Now, let us consider our LFUCache class:

Function __init__

3 things to maintain:

  1. a dict, named as self._node, for the reference of all nodes given key. That is, O(1) time to retrieve node given a key.
  2. Each frequency has a doubly linked list, store in self._freq, where key is the frequency, and value is an object of DList
  3. The min frequency through all nodes. We can maintain this in O(1) time, taking advantage of the fact that the frequency can only increment by 1. Use the followingtwo rules:

Rule 1: Whenever we see the size of the DList of current min frequency is 0, the min frequency must increment by 1.

Rule 2: Whenever put in a new (key, value), the min frequency must be equal to 1 (the new node)

Function _update(self, node):

This is a helper function that used in the following two cases:

  1. when get(key) is called and
  2. when put(key, value) is called and the key exists.

The common point of these two cases is that

  1. no new node comes in, and
  2. the node is visited one more times -> node.freq changed thus the place of this node will change.

The logic of this function is:

  1. pop the node from the old DList (with freq f)
  2. append the node to new DList (with freq f+1)
  3. if old DList has size 0 and self._minfreq is f, update self._minfreq to f+1.
Function get(key)

Through checking self._node[key], we can get the node in O(1) time. Just performs self._update, then we can return the value of node.

Function put(key, value)

If key already exists in self._node, we do the same operations as get, except updating the node.val to new value. Otherwise, the following logic will be performed

  1. if the cache reaches its capacity, pop the least frequently used item. How we pop it: we maintain the self._minfreq, the minimum possible frequency in cache. All cache with the same frequency are stored as a DList with recently used order (Always append at head). So, the tail of the DList with self._minfreq is the least recently used one, pop it.
  2. add new node to self._node
  3. add new node to the DList with frequency 1
  4. reset self._minfreq to 1

Complexity

Time complexity of all operations is O(1).

Code

class ListNode:
    def __init__(self, key = None, val=0, freq = 1, nxt=None, prv=None):
        self.val = val
        self.key = key
        self.next = nxt
        self.prev = prv
        self.freq = freq

class DList:
    def __init__(self):
        self.head = ListNode() # dummy node
        self.head.next = self.head.prev = self.head
        self._size = 0
    
    def __len__(self):
        return self._size
    
    def append(self, node):
        node.next = self.head.next
        node.prev = self.head
        node.next.prev = node
        self.head.next = node
        self._size += 1
    
    def pop(self, node=None):
        if self._size == 0: return
        
        if not node: node = self.head.prev

        node.prev.next = node.next
        node.next.prev = node.prev
        self._size -= 1
        
        return node
        
class LFUCache:
    def __init__(self, capacity):
        self._size = 0
        self._capacity = capacity
        self._node = dict() # key: Node
        self._freq = defaultdict(DList)
        self._minfreq = 0 
        
    def _update(self, node):
        freq = node.freq
        
        self._freq[freq].pop(node)
        if self._minfreq == freq and not self._freq[freq]:
            self._minfreq += 1
        
        node.freq += 1
        freq = node.freq
        self._freq[freq].append(node)
    
    def get(self, key):
        if key not in self._node: return -1
        
        node = self._node[key]
        self._update(node)
        return node.val

    def put(self, key, value):
        if self._capacity == 0:
            return
        
        if key in self._node:
            node = self._node[key]
            self._update(node)
            node.val = value
        else:
            if self._size == self._capacity:
                node = self._freq[self._minfreq].pop()
                del self._node[node.key]
                self._size -= 1
                
            node = ListNode(key, value)
            self._node[key] = node
            self._freq[1].append(node)
            self._minfreq = 1
            self._size += 1