Implementing LFU Cache like Building a Lego

In the previous article Handwriting the LRU Algorithm, we discussed the implementation of the LRU (Least Recently Used) cache eviction algorithm. This article will cover another famous cache eviction algorithm: the LFU (Least Frequently Used) algorithm.

The LRU algorithm's eviction strategy is to remove the data that has not been used for the longest time. In contrast, the LFU algorithm's eviction strategy is to remove the data that has been used the least frequently.

The core data structure of the LRU algorithm is a hash-linked list (LinkedHashMap). By leveraging the ordered nature of the linked list, elements maintain their insertion order, and with the quick access capability of hash mapping, we can access any element in the list in O(1) time.

In terms of implementation complexity, the LFU algorithm is more challenging than the LRU algorithm. The LRU algorithm essentially sorts data by time, which can be naturally achieved using a linked list. When you continuously add elements to the head of the list, the closer an element is to the head, the newer it is. Conversely, the closer it is to the tail, the older it is. When we perform cache eviction, we simply remove the element at the tail.

On the other hand, the LFU algorithm sorts data by access frequency, which is not as straightforward. Furthermore, if multiple pieces of data have the same access frequency, we need to evict the data that was inserted earliest. This means the LFU algorithm evicts the data with the lowest access frequency, and if there are multiple such data, it evicts the oldest among them.

Therefore, the LFU algorithm is considerably more complex and frequently appears in interviews because it is commonly used in engineering practice. It might also be because the LRU algorithm is relatively simple. That being said, the patterns of these famous algorithms are fixed; the key challenge lies in writing clean and bug-free code due to the complex logic involved.

In this article, I will break down the LFU algorithm step by step, from top to bottom, as a surefire way to tackle complex problems.

1. Algorithm Description

You are required to write a class that accepts a capacity parameter and implements the get and put methods:

class LFUCache {
    // construct a cache with capacity
    public LFUCache(int capacity) {}
    // query key in the cache
    public int get(int key) {}
    // store key and val in the cache
    public void put(int key, int val) {}
}

class LFUCache {
public:
    // construct a cache with capacity
    LFUCache(int capacity) {}
    // query key in the cache
    int get(int key) {}
    // put key and val into the cache
    void put(int key, int val) {}
};

class LFUCache:
    def __init__(self, capacity: int):
        # construct a cache with capacity
        pass

    def get(self, key: int) -> int:
        # query key in the cache
        pass

    def put(self, key: int, val: int) -> None:
        # store key and val in the cache
        pass

type LFUCache struct {
}

// construct a cache with capacity
func Constructor(capacity int) *LFUCache {
    return &LFUCache{}
}

// Get queries the key from the cache and returns its
// corresponding value. If the key does not exist, it returns
func (c *LFUCache) Get(key int) int {
    return 0
}

// Put stores the key and value into the cache. If the capacity is full,
// it needs to delete the least frequently used element from the cache.
func (c *LFUCache) Put(key int, value int) {

}

var LFUCache = function (capacity) {
    // construct a cache with capacity 'capacity'
}
LFUCache.prototype.get = function (key) {
    // query the key in the cache
}
LFUCache.prototype.put = function (key, val) {
    // put the key and value into the cache
}

The get(key) method searches for the key key in the cache. If key exists, it returns the corresponding val; otherwise, it returns -1.

The put(key, value) method inserts or updates the cache. If key already exists, it updates its value to val; if key does not exist, it inserts the key-value pair (key, val).

When the cache reaches its capacity, before inserting a new key-value pair, it should delete the key-value pair with the lowest frequency of use (denoted by freq). If there are multiple key-value pairs with the lowest freq, the oldest one should be deleted.

// construct an LFU cache with a capacity of 2
LFUCache cache = new LFUCache(2);

// insert two pairs (key, val), with corresponding freq being 1
cache.put(1, 10);
cache.put(2, 20);

// query the value corresponding to key 1
// return 10, and the freq of key 1 becomes 2
cache.get(1);

// cache is full, evict the key 2 with the smallest freq
// insert the key-value pair (3, 30), with corresponding freq being 1
cache.put(3, 30);   

// key 2 has been evicted, return -1
cache.get(2);

// Construct an LFU cache with a capacity of 2
LFUCache cache(2);

// Insert two pairs (key, val), their freq is 1
cache.put(1, 10);
cache.put(2, 20);

// Query the val corresponding to key 1
// Return 10, and the freq of key 1 becomes 2
cache.get(1);

// Capacity is full, eliminate the key 2 with the smallest freq
// Insert the key-value pair (3, 30), its freq is 1
cache.put(3, 30);   

// Key 2 has been eliminated, return -1
cache.get(2);

# Construct an LFU cache with a capacity of 2
cache = LFUCache(2)

# Insert two pairs (key, val), both with a frequency of 1
cache.put(1, 10)
cache.put(2, 20)

# Query the value corresponding to key 1
# Return 10, and the frequency of key 1 becomes 2
cache.get(1)

# Capacity is full, evict the key with the smallest frequency, which is 2
# Insert the key-value pair (3, 30), with a frequency of 1
cache.put(3, 30)   

# Key 2 has already been evicted, return -1
cache.get(2)

// construct an LFU cache with a capacity of 2
cache := Constructor(2)

// insert two pairs (key, val), their freq is 1
cache.Put(1, 10)
cache.Put(2, 20)

// query the value corresponding to key 1
// returns 10, and the freq of key 1 becomes 2
cache.Get(1)

// capacity is full, evict the key 2 with the smallest freq
// insert the key-value pair (3, 30), its freq is 1
cache.Put(3, 30)   

// key 2 has been evicted and deleted, returns -1
cache.Get(2)

// construct an LFU cache with capacity 2
var cache = new LFUCache(2);

// insert two pairs (key, val), with freq being 1
cache.put(1, 10);
cache.put(2, 20);

// query the val corresponding to key 1
// return 10, and the freq of key 1 becomes 2
cache.get(1);

// capacity is full, evict the key 2 with the smallest freq
// insert key-value pair (3, 30), with freq being 1
cache.put(3, 30);   

// key 2 has been evicted, return -1
cache.get(2);

2. Thought Process Analysis

Let's start with the basics. According to the LFU algorithm logic, here are some obvious facts during the execution:

1. When calling the get(key) method, it should return the val corresponding to that key.

2. Each time a key is accessed using get or put methods, the freq of that key should increase by one.

3. If an insertion occurs when the capacity is full, the key with the smallest freq should be removed. If there are multiple keys with the same smallest freq, remove the oldest one.

To address these requirements in O(1) time, we can use basic data structures to tackle each point:

1. Use a HashMap to store the mapping from key to val, allowing for quick computation of get(key).

HashMap<Integer, Integer> keyToVal;

unordered_map<int, int> keyToVal;

keyToVal = {}

keyToVal := make(map[int]int)

var keyToVal = new Map();

2. Use a HashMap to store the mapping from key to freq, which allows quick operations on the freq corresponding to the key.

HashMap<Integer, Integer> keyToFreq;

unordered_map<int, int> keyToFreq;

keyToFreq = {}

keyToFreq := make(map[int]int)

var keyToFreq = new Map();

3. This requirement is probably the core of the LFU algorithm, so let's discuss it separately: