Implement an LFU Cache

In this tutorial, we'll discuss implementing an LFU (Least Frequently Used) cache. Here's what we'll cover:

What is an LFU Cache?

A brief overview of how an LFU cache works and why it's useful.

How is it Different from LRU Cache?

We'll explain the difference between LFU and LRU caching strategies.

Required Operations

The key operations we need to implement for an LFU cache.

Implementation #1: HashMap

A first pass implementation using a HashMap.

Implementation #2: Singly Linked List

An improved version using a linked list for tracking order.

Implementation #3: Doubly Linked List

Final implementation with a doubly linked list structure.

Alright, let's get started!

LFU Cache

Least Frequently Used or LFU cache is a cache algorithm that manages the replacement of blocks in a cache. The algorithm keeps track of the number of times a block of memory is referenced, and replaces the block with the least frequency once the cache is full.

How LFU Cache is Different From LRU Cache?

The primary difference between Least Frequently and Least Recently Used cache is that the former evicts the memory block with the lowest frequency, even if the block is just recently accessed. Whereas the latter removes the memory block that has not been referenced for the longest time.

Also, check out, Design an LRU Cache.

Design an LFU Cache

The problem statement is to design a data structure for an LFU cache. Our LFUCache class should perform the following operations:

LFUCache(int n)

The constructor initializes the cache object with the required capacity.

int get(int key)

This method gets the value of the key if the key exists in the cache. If not, it returns -1.

void put(int key, int value)

This method does the following:

• If the key is present, it updates the value of the key.
• If the key is not present, it inserts the key along with the value.
• If the cache becomes full, it removes the least frequently used key, and then inserts a new element.
• If the cache becomes full, and there's a tie between the least frequently used key, then the least recently used key would be invalidated.

LFU cache evicts the memory block that has been least recently accessed.

Implement an LFU Cache Using HashMap

Before moving on to designing the cache using HashMap, let's look at a straightforward approach to implementing an LFU Cache:

• First, initialize an array with the required capacity.
• Each element in an array should contain fields to store key, value, frequency, and timestamp.
• In order to get an element with a particular key, traverse the array, if the element exists, return it, otherwise return -1. The worst-case complexity, in this case, is O(n).
• To insert an element into the array, there can be two possibilities.
• If the array is not full, and the key doesn't exists already, insert the element with frequency 1 and timestamp 0. Update the timestamp of the remaining elements in the array.
• If the array is full, traverse the entire array to find the element with the least frequency to remove it. If there's a tie, then remove the element with the highest timestamp.
• Now insert the new element.

Now, let's discuss a better approach using HashMap.

Here, we'll use maps. One will be to store key-value pairs, and the other to store the count of the times a block is referenced from the cache. In other words, a value is accessed from the key-value map: java private Map<Integer, Integer> valueMap = new HashMap<>(); private Map<Integer, Integer> countMap = new HashMap<>(); javascript let valueMap = new Map(); let countMap = new Map(); python valueMap = dict() countMap = dict() cpp std::map<int, int> valueMap; std::map<int, int> countMap; csharp private Dictionary<int, int> valueMap = new Dictionary<int, int>(); private Dictionary<int, int> countMap = new Dictionary<int, int>(); go valueMap := make(map[int]int) countMap := make(map[int]int)

LFU cache constructor will look like the following: ```java public LFUCache(int n) {

size = n;

} javascript LFUCache = function(n) { this.size = n; } python def init(self, n): self.size = n cpp LFUCache::LFUCache(int n) { size = n; } csharp public LFUCache(int n) { size = n; } go type LFUCache struct { size int }

func Constructor(n int) LFUCache { return LFUCache{n} } To get an element from the valueMap, the implementation is straightforward: java public int get(int key) {

if (!valueMap.containsKey(key) || size==0) {
    return -1;
}

countMap.put(key, countMap.get(key) + 1);
return valueMap.get(key);

} javascript get(key) {

if (!this.valueMap.has(key) || this.size == 0) {
    return -1;
}

this.countMap.set(key, this.countMap.get(key) + 1);
return this.valueMap.get(key);

} python def get(self, key):

if key not in self.value_map or self.size == 0:
    return -1

self.count_map[key] = self.count_map[key] + 1
return self.value_map[key]

```cpp
int get(int key) {

    if (!valueMap.count(key) || size == 0) {
        return -1;
    }

    countMap[key] = countMap[key] + 1;
    return valueMap[key];

}

public int Get(int key) {

    if (!valueMap.ContainsKey(key) || size == 0) {
        return -1;
    }

    countMap[key] = countMap[key] + 1;
    return valueMap[key];

}

func (c *counter) get(key int) int {

    if _, ok := c.valueMap[key]; !ok || c.size == 0 {
        return -1
    }

    c.countMap[key] = c.countMap[key] + 1
    return c.valueMap[key]

}

*If you want to access an element, it will only take O(1) time. *

Now, it's time to insert an element in the cache. We've multiple things to consider here:

• If the key already exists, just update the value in valueMap and increment the count in countMap. This will take O(1) time.
• If the key doesn't exists, and the size of the countMap hasn't reached it's maximum capacity, then insert the key and value in valueMap, and set the count to 1 in countMap. This will take O(1) time.
• Now,there can be a case when the cache is full. To handle this, iterate through the countMap to find the key with the lowest count, then remove that entry from both the countMap and the valueMap. This will take O(n) time.

public void put(int key, int value) {

    if (!valueMap.containsKey(key) && size>0) {

        if (valueMap.size() == size) {

            // find the key with the lowest count
            Entry<Integer, Integer> lowestCountEntry = countMap.entrySet().iterator().next();
            int lowestCountKey = lowestCountEntry.getKey();

            for (Entry<Integer, Integer> entry : countMap.entrySet()) {

                if (entry.getValue() < lowestCountEntry.getValue()) {

                    lowestCountKey = entry.getKey();

                }

            }

            countMap.remove(lowestCountKey);
                        valueMap.remove(lowestCountKey);

        }

        valueMap.put(key, value);
        countMap.put(key, 1);

    } else if(size>0){

        valueMap.put(key, value);
        countMap.put(key, countMap.get(key) + 1);

    }

}

put(key, value) {
    if (!this.valueMap.has(key) && this.size > 0) {
        if (this.valueMap.size === this.size) {
            let lowestCountEntry = this.countMap.entries().next().value;
            let lowestCountKey = lowestCountEntry[0];
            for (let entry of this.countMap.entries()) {
                if (entry[1] < lowestCountEntry[1]) {
                    lowestCountKey = entry[0];
                }
            }
            this.countMap.delete(lowestCountKey);
            this.valueMap.delete(lowestCountKey);
        }
        this.valueMap.set(key, value);
        this.countMap.set(key, 1);
    } else if (this.size > 0) {
        this.valueMap.set(key, value);
        this.countMap.set(key, this.countMap.get(key) + 1);
    }
}

def put(self, key, value):
    if key not in self.value_map and self.size > 0:
        if len(self.value_map) == self.size:
            lowest_count_key = min(self.count_map.items(), key=lambda x: x[1])[0]
            del self.count_map[lowest_count_key]
            del self.value_map[lowest_count_key]
        self.value_map[key] = value
        self.count_map[key] = 1
    elif self.size > 0:
        self.value_map[key] = value
        self.count_map[key] += 1

void put(int key, int value) {
    if (valueMap.find(key) == valueMap.end() && size > 0) {
        if (valueMap.size() == size) {
            auto lowestCountKey = min_element(countMap.begin(), countMap.end(), [](const auto& l, const auto& r) { return l.second < r.second; })->first;
            countMap.erase(lowestCountKey);
            valueMap.erase(lowestCountKey);
        }
        valueMap[key] = value;
        countMap[key] = 1;
    } else if (size > 0) {
        valueMap[key] = value;
        countMap[key]++;
    }
}

public void Put(int key, int value) {
    if (!valueMap.ContainsKey(key) && size > 0) {
        if (valueMap.Count == size) {
            var lowestCountKey = countMap.OrderBy(kvp => kvp.Value).First().Key;
            countMap.Remove(lowestCountKey);
            valueMap.Remove(lowestCountKey);
        }
        valueMap[key] = value;
        countMap[key] = 1;
    } else if (size > 0) {
        valueMap[key] = value;
        countMap[key] = countMap[key] + 1;
    }
}

func (this *objName) Put(key int, value int) {
    if _, ok := this.valueMap[key]; !ok && this.size > 0 {
        if len(this.valueMap) == this.size {
            lowestCountKey := getMinKey(this.countMap)
            delete(this.countMap, lowestCountKey)
            delete(this.valueMap, lowestCountKey)
        }
        this.valueMap[key] = value
        this.countMap[key] = 1
    } else if this.size > 0 {
        this.valueMap[key] = value
        this.countMap[key]++
    }
}
func getMinKey(m map[int]int) (minkey int) {
    minval := int(^uint(0) >> 1)
    for k, v := range m {
        if v < minval {
            minkey, minval = k, v
        }
    }
    return minkey
}

Note that there's a problem here. If there exists multiple keys with the same count, then this solution will not work as HashMap doesn't keep track of the insertion order.

With this, we'll move to our next implementation in which we'll be using a Singly Linked List to handle this issue.

HashMap keeps the track of insertion order of elements.

Implement an LFU Cache Using Singly Linked List

Here, we'll introduce a new data structure in which we'll insert the key as the count, and value as the list of elements with the same count. For this we'll be using TreeMap as it will store the count in sorted order: java private TreeMap<Integer, List<Integer>> sortedCountMap = new TreeMap<>(); csharp private SortedDictionary<int, List<int>> sortedCountMap = new SortedDictionary<int, List<int>>(); javascript let sortedCountMap = new Map(); python sorted_count_map = {} cpp std::map<int, std::list<int>> sortedCountMap; go sortedCountMap := make(map[int][]int) Now accessing the element that has been least recently accessed along with the lowest count will become straightforward. The first key in sortedCountMap will be the lowest frequency. Now to find the element that has been least recently accessed with that frequency, all you have to do is remove the first element from that list. This will take O(1) time.

Now, let's discuss the steps that are different from our previous implementation to get an element:

• First, we'll find the count from the countMap.
• Next, we'll remove the key from the sortedCountMap, and insert it again with a new count value.
• Note that we'll remove the entry of the previous count from the sortedCountMap if that element was the only element in the list.

private void removeEntryFromSortedCountMapIfListIsEmpty(int count) {

    if (sortedCountMap.get(count).size() == 0) {

        sortedCountMap.remove(count);
    }               
}

private removeEntryFromSortedCountMapIfListIsEmpty(count) {
    if (this.sortedCountMap.get(count).size() === 0) {
        this.sortedCountMap.remove(count);
    }
}

def remove_entry_from_sorted_count_map_if_list_is_empty(self, count):
    if len(self.sorted_count_map.get(count)) == 0:
        self.sorted_count_map.remove(count)

private:
void removeEntryFromSortedCountMapIfListIsEmpty(int count) {
    if (sortedCountMap[count].size() == 0) {
        sortedCountMap.erase(count);
    }
}

private void RemoveEntryFromSortedCountMapIfListIsEmpty(int count)
{
    if (SortedCountMap[count].Count == 0)
    {
        SortedCountMap.Remove(count);
    }
}

func (m *MyStruct) removeEntryFromSortedCountMapIfListIsEmpty(count int) {
    if len(m.sortedCountMap[count]) == 0 {
        delete(m.sortedCountMap, count)
    }
}

public int get(int key) {

    if (!valueMap.containsKey(key) || size == 0) {
        return -1;
    }

    int count = countMap.get(key);
    sortedCountMap.get(count).remove(new Integer(key));
    removeEntryFromSortedCountMapIfListIsEmpty(count);

    sortedCountMap.computeIfAbsent(count + 1, k -> new LinkedList<>()).add(key);

    countMap.put(key, countMap.get(key) + 1);

    return valueMap.get(key);

}

get(key) {

    if (!this.valueMap.has(key) || this.size === 0) {
        return -1;
    }

    let count = this.countMap.get(key);
    this.sortedCountMap.get(count).delete(key);
    this.removeEntryFromSortedCountMapIfListIsEmpty(count);

    if (!this.sortedCountMap.has(count + 1)) {
        this.sortedCountMap.set(count + 1, new LinkedList());
    }
    this.sortedCountMap.get(count + 1).add(key);

    this.countMap.set(key, this.countMap.get(key) + 1);

    return this.valueMap.get(key);

}

def get(self, key):

    if not key in self.valueMap or self.size == 0:
        return -1

    count = self.countMap[key]
    self.sortedCountMap[count].remove(key)
    self.removeEntryFromSortedCountMapIfListIsEmpty(count)

    if not count + 1 in self.sortedCountMap:
        self.sortedCountMap[count + 1] = LinkedList()
    self.sortedCountMap[count + 1].add(key)

    self.countMap[key] = self.countMap[key] + 1

    return self.valueMap[key]

public int get(int key) {

    if (valueMap.find(key) == valueMap.end() || size == 0) {
        return -1;
    }

    int count = countMap[key];
    sortedCountMap[count].remove(key);
    removeEntryFromSortedCountMapIfListIsEmpty(count);

    if (sortedCountMap.find(count + 1) == sortedCountMap.end()) {
        sortedCountMap[count + 1] = LinkedList<int>();
    }
    sortedCountMap[count + 1].push_back(key);

    countMap[key] = countMap[key] + 1;

    return valueMap[key];

}

public int Get(int key) {

    if (!valueMap.ContainsKey(key) || size == 0) {
        return -1;
    }

    int count = countMap[key];
    sortedCountMap[count].Remove(key);
    RemoveEntryFromSortedCountMapIfListIsEmpty(count);

    if (!sortedCountMap.ContainsKey(count + 1)) {
        sortedCountMap[count + 1] = new LinkedList<int>();
    }
    sortedCountMap[count + 1].AddLast(key);

    countMap[key] = countMap[key] + 1;

    return valueMap[key];

}

func (cache *LRUCache) Get(key int) int {

    if _, ok := cache.valueMap[key]; !ok || cache.size == 0 {
        return -1
    }

    count := cache.countMap[key]
    val := cache.sortedCountMap[count].Remove(key)
    cache.sortedCountMap[count].PushBack(val)

    if _, ok := cache.sortedCountMap[count+1]; !ok {
        cache.sortedCountMap[count+1] = list.New()
    }
    cache.sortedCountMap[count+1].PushBack(val)

    cache.countMap[key] = cache.countMap[key] + 1

    return cache.valueMap[key]

}

Let's discuss the steps that are different from our previous implementation to insert an element:

If the key doesn't exist, and the cache is full, the eviction strategy will be different now:

• We'll first remove the least frequently used key from the sortedCountMap.
• Next, we'll also remove that entry from the sortedCountMap if that key was the only element in the list.
• After that, we'll remove the key/value pair from both the countMap and the valueMap.
• Finally, we'll update the countMap, valueMap, and sortedCountMap.

Let's discuss the case, when the key already exists:

• Now, we'll update the position of the key in sortedCountMap.
• We'll also remove the entry if the key was the only element in the list with that previous count value.

public void put(int key, int value) {

    if (!valueMap.containsKey(key) && size > 0) {
        if (valueMap.size() == size) {

            int lowestFrequency = sortedCountMap.firstKey();
            int evictKey = sortedCountMap.get(lowestFrequency).remove(0);
                removeEntryFromSortedCountMapIfListIsEmpty(lowestFrequency);

            valueMap.remove(evictKey);
            countMap.remove(evictKey);

        }

        valueMap.put(key, value);
        countMap.put(key, 1);
        sortedCountMap.computeIfAbsent(1, k -> new LinkedList<>()).add(key);

    } else if (valueMap.containsKey(key) && size > 0) {

        int count = countMap.get(key);

        valueMap.put(key, value);
        countMap.put(key, count + 1);

        sortedCountMap.get(count).remove(new Integer(key));
        removeEntryFromSortedCountMapIfListIsEmpty(count);
        sortedCountMap.computeIfAbsent(count + 1, k -> new LinkedList<>()).add(key);

    }

}

put(key, value) {
  if (!this.valueMap.has(key) && this.size > 0) {
    if (this.valueMap.size === this.size) {
      let lowestFrequency = [...this.sortedCountMap.keys()][0];
      let evictKey = this.sortedCountMap.get(lowestFrequency).shift();
      if (!this.sortedCountMap.get(lowestFrequency).length) {
        this.sortedCountMap.delete(lowestFrequency);
      }
      this.valueMap.delete(evictKey);
      this.countMap.delete(evictKey);
    }
    this.valueMap.set(key, value);
    this.countMap.set(key, 1);
    if (!this.sortedCountMap.has(1)) {
      this.sortedCountMap.set(1, []);
    }
    this.sortedCountMap.get(1).push(key);
  } else if (this.valueMap.has(key) && this.size > 0) {
    let count = this.countMap.get(key);
    this.valueMap.set(key, value);
    this.countMap.set(key, count + 1);
    this.sortedCountMap.get(count).remove(key);
    if (!this.sortedCountMap.get(count).length) {
      this.sortedCountMap.delete(count);
    }
    if (!this.sortedCountMap.has(count + 1)) {
      this.sortedCountMap.set(count + 1, []);
    }
    this.sortedCountMap.get(count + 1).push(key);
  }
}

def put(self, key, value):
  if not key in self.value_map and self.size > 0:
    if len(self.value_map) == self.size:
      lowest_frequency = min(self.sorted_count_map.keys())
      evict_key = self.sorted_count_map[lowest_frequency].pop(0)
      if len(self.sorted_count_map[lowest_frequency]) == 0:
        del self.sorted_count_map[lowest_frequency]
      del self.value_map[evict_key]
      del self.count_map[evict_key]
    self.value_map[key] = value
    self.count_map[key] = 1
    if not 1 in self.sorted_count_map:
        self.sorted_count_map[1] = []
    self.sorted_count_map[1].append(key)
  elif key in self.value_map and self.size > 0:
    count = self.count_map[key]
    self.value_map[key] = value
    self.count_map[key] = count + 1
    self.sorted_count_map[count].remove(key)
    if len(self.sorted_count_map[count]) == 0:
        del self.sorted_count_map[count]
    if not count+1 in self.sorted_count_map:
        self.sorted_count_map[count+1] = []
    self.sorted_count_map[count+1].append(key)

void put(int key, int value) {
  if (valueMap.count(key) == 0 && size > 0) {
    if (valueMap.size() == size) {
      int lowestFrequency = sortedCountMap.begin()->first;
      std::list<int>& evictKeys = sortedCountMap[lowestFrequency];
      int evictKey = evictKeys.front();
      evictKeys.pop_front();
      if (evictKeys.empty())
        sortedCountMap.erase(lowestFrequency);
      valueMap.erase(evictKey);
      countMap.erase(evictKey);
    }
    valueMap[key] = value;
    countMap[key] = 1;
    sortedCountMap[1].push_back(key);
  } else if (valueMap.count(key) == 1 && size > 0) {
    int count = countMap[key];
    valueMap[key] = value;
    countMap[key] = count + 1;
    sortedCountMap[count].remove(key);
    if (sortedCountMap[count].empty())
      sortedCountMap.erase(count);
    sortedCountMap[count + 1].push_back(key);
  }
}

public void Put(int key, int value)
{
  if (!ValueMap.ContainsKey(key) && Size > 0)
  {
    if (ValueMap.Count == Size)
    {
      var lowestFrequency = SortedCountMap.Keys.First();
      var evictKey = SortedCountMap[lowestFrequency].First();
      SortedCountMap[lowestFrequency].RemoveAt(0);
      if (SortedCountMap[lowestFrequency].Count == 0)
      {
        SortedCountMap.Remove(lowestFrequency);
      }
      ValueMap.Remove(evictKey);
      CountMap.Remove(evictKey);
    }
    ValueMap.Add(key, value);
    CountMap.Add(key, 1);
    if (!SortedCountMap.ContainsKey(1))
    {
      SortedCountMap.Add(1, new List<int>());
    }
    SortedCountMap[1].Add(key);
  }
  else if (ValueMap.ContainsKey(key) && Size > 0)
  {
    int count = CountMap[key];
    ValueMap[key] = value;
    CountMap[key] = ++count;
    SortedCountMap[count-1].Remove(key);
    if (!SortedCountMap[count-1].Any())
    {
      SortedCountMap.Remove(count-1);
    }
    if (!SortedCountMap.ContainsKey(count))
    {
      SortedCountMap.Add(count, new List<int>());
    }
    SortedCountMap[count].Add(key);
  }
}

func (cache *LFUCache) Put(key int, value int) {
  if _, exist := cache.values[key]; exist && cache.cap > 0 {
    count := cache.counts[key]
    cache.values[key] = value
    cache.counts[key] = count + 1
    cache.lists[count] = remove(cache.lists[count], key)
    if len(cache.lists[count]) == 0 {
      delete(cache.lists, count)
    }
    if _, exist := cache.lists[count+1]; !exist {
      cache.lists[count+1] = make(queue, 0)
    }
    cache.lists[count+1] = append(cache.lists[count+1], key)
  } else if !exist && cache.cap > 0 {
    if len(cache.values) == cache.cap {
      min := cache.min
      evictKey := cache.lists[min][0]
      cache.lists[min] = cache.lists[min][1:]
      if len(cache.lists[min]) == 0 {
        delete(cache.lists, min)
      }
      delete(cache.values, evictKey)
      delete(cache.counts, evictKey)
    }
    cache.values[key] = value
    cache.counts[key] = 1
    if _, exist := cache.lists[1]; !exist {
      cache.lists[1] = make(queue, 0)
    }
    cache.lists[1] = append(cache.lists[1], key)
    cache.min = 1
  }
}

There exists a problem in this implementation.

The keys having the same count are in a list. Now to access a key, inorder to update it's entry in the sortedCountMap, we'll have to iterate through the entire list. The worst complexity in this case will be O(n).

To solve this problem, we'll move to our next implementation.

Implement an LFU Cache Using Doubly Linked List

To avoid iterating through the whole list, remove the element directly, and insert it against other count value sortedCountMap, we'll be needing a Doubly Linked List. Note that this will now take O(1) time.

private TreeMap<Integer, DoubleLinkedList> sortedCountMap = new TreeMap<>();

let sortedCountMap = new Map();

sorted_count_map = {}

std::map<int, DoubleLinkedList> sortedCountMap;

private SortedDictionary<int, DoubleLinkedList> sortedCountMap = new SortedDictionary<int, DoubleLinkedList>();

var sortedCountMap = make(map[int]*DoubleLinkedList)

Here, we'll store Node object as the value in valueMap. It will have key, value, and the position of the node in the linked list stored as the value in sortedCountMap: java private Map<Integer, Node> valueMap = new HashMap<>(); csharp private Dictionary<int, Node> valueMap = new Dictionary<int, Node>(); go valueMap := make(map[int]Node) javascript var valueMap = {}; python value_map = {} cpp std::map<int, Node> valueMap;

public class Node {

private int key;
private int value;
Node next;
Node previous;

public Node(int key, int value) {
    super();
    this.key = key;
    this.value = value;

}

class Node {
    constructor(key, value) {
        super();
        this.key = key;
        this.value = value;
    }
}

class Node:
    def __init__(self, key, value):
        super().__init__()
        self.key = key
        self.value = value
        self.next = None
        self.previous = None

class Node {
private:
    int key;
    int value;
    Node* next;
    Node* previous;

public:
    Node(int key, int value) {
        this->key = key;
        this->value = value;
    }
};

public class Node {
    private int key;
    private int value;
    public Node next;
    public Node previous;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

type Node struct {
    key      int
    value    int
    next     *Node
    previous *Node
}

func NewNode(key int, value int) *Node {
    return &Node{
        key:   key,
        value: value,
    }
}

Let's have a look at the DoubleLinkedList class:

public class DoubleLinkedList {

private int n;
Node head;
Node tail;

public void add(Node node) {

    if (head == null) {

        head = node;
    }

    else {

        tail.next = node;
        node.previous = tail;

    }
    tail = node;
    n++;

}

public void remove(Node node) {

    if (node.next == null) {
        tail = node.previous;

    } else {

        node.next.previous = node.previous;

    }

    if (node.previous == null) {

        head = node.next;
    } else {

        node.previous.next = node.next;
    }

    n--;

}

public int size() {

    return n;

}

public Node getHead() {
    return head;
}

}

class DoubleLinkedList {

  constructor(){
    this.n = 0;
    this.head = null;
    this.tail = null;
  }

  add(node) {

    if (this.head == null) {

      this.head = node;
    }

    else {

      this.tail.next = node;
      node.previous = this.tail;

    }
    this.tail = node;
    this.n++;

  }

  remove(node) {

    if (node.next == null) {
      this.tail = node.previous;

    } else {

      node.next.previous = node.previous;

    }

    if (node.previous == null) {

      this.head = node.next;
    } else {

      node.previous.next = node.next;

    }

    this.n--;

  }

  size() {

    return this.n;

  }

  getHead() {
    return this.head;
  }

}

class DoubleLinkedList:

  def __init__(self):
    self.n = 0
    self.head = None
    self.tail = None

  def add(self, node):

    if self.head is None:

      self.head = node

    else:

      self.tail.next = node
      node.previous = self.tail

    self.tail = node
    self.n += 1

  def remove(self, node):

    if node.next is None:
      self.tail = node.previous

    else:

      node.next.previous = node.previous

    if node.previous is None:

      self.head = node.next
    else:

      node.previous.next = node.next

    self.n -= 1

  def size(self):

    return self.n

  def get_head(self):
    return self.head

class DoubleLinkedList {

private:
    int n;
    Node* head;
    Node* tail;

public:

    DoubleLinkedList() : n(0), head(nullptr), tail(nullptr) {}

    void add(Node* node) {

        if (head == nullptr) {

            head = node;
        }

        else {

            tail->next = node;
            node->previous = tail;

        }
        tail = node;
        n++;

    }

    void remove(Node* node) {

        if (node->next == nullptr) {
            tail = node->previous;

        } else {

            node->next->previous = node->previous;

        }

        if (node->previous == nullptr) {

            head = node->next;
        } else {

            node->previous->next = node->next;

        }

        n--;

    }

    int size() {

        return n;

    }

    Node* getHead() {
        return head;
    }

};

public class DoubleLinkedList {

private int n;
Node head;
Node tail;

public void Add(Node node) {

    if (head == null) {

        head = node;
    }

    else {

        tail.next = node;
        node.previous = tail;

    }
    tail = node;
    n++;

}

public void Remove(Node node) {

    if (node.next == null) {
        tail = node.previous;

    } else {

        node.next.previous = node.previous;

    }

    if (node.previous == null) {

        head = node.next;
    } else {

        node.previous.next = node.next;

    }

    n--;

}

public int Size() {

    return n;

}

public Node GetHead() {
    return head;
}

}

package main

type Node struct {
    next     *Node
    previous *Node
}

type DoubleLinkedList struct {
    n    int
    head *Node
    tail *Node
}

func (dll *DoubleLinkedList) Add(node *Node) {

    if dll.head == nil {

        dll.head = node
    } else {

        dll.tail.next = node
        node.previous = dll.tail

    }
    dll.tail = node
    dll.n++

}

func (dll *DoubleLinkedList) Remove(node *Node) {

    if node.next == nil {
        dll.tail = node.previous

    } else {

        node.next.previous = node.previous

    }

    if node.previous == nil {

        dll.head = node.next
    } else {

        node.previous.next = node.next

    }

    dll.n--

}

func (dll *DoubleLinkedList) Size() int {

    return dll.n

}

func (dll *DoubleLinkedList) GetHead() *Node {
    return dll.head
}

To get an element, and update the value in sortedCountMap takes O(1) time now: java public int get(int key) { if (!valueMap.containsKey(key) || size == 0) { return -1; } Node nodeToRemove = valueMap.get(key); Node node = new Node(key, nodeToRemove.getValue()); int count = countMap.get(key); sortedCountMap.get(count).remove(nodeToRemove); removeEntryFromSortedCountMapIfListIsEmpty(count); valueMap.remove(key); countMap.remove(key); valueMap.put(key, node); countMap.put(key, count + 1); sortedCountMap.computeIfAbsent(count + 1, k -> new DoubleLinkedList()).add(node); return valueMap.get(key).getValue(); } javascript get(key) { if (!this.valueMap.has(key) || this.size === 0) { return -1; } let nodeToRemove = this.valueMap.get(key); let node = new Node(key, nodeToRemove.value); let count = this.countMap.get(key); this.sortedCountMap.get(count).remove(nodeToRemove); this.removeEntryFromSortedCountMapIfListIsEmpty(count); this.valueMap.delete(key); this.countMap.delete(key); this.valueMap.set(key, node); this.countMap.set(key, count + 1); this.sortedCountMap.set(count + 1, this.sortedCountMap.get(count + 1) || new DoubleLinkedList()); this.sortedCountMap.get(count + 1).add(node); return this.valueMap.get(key).value; } python def get(self, key): if key not in self.value_map or self.size == 0: return -1 node_to_remove = self.value_map[key] node = Node(key, node_to_remove.value) count = self.count_map[key] self.sorted_count_map[count].remove(node_to_remove) self.remove_entry_from_sorted_count_map_if_list_is_empty(count) del self.value_map[key] del self.count_map[key] self.value_map[key] = node self.count_map[key] = count + 1 if count + 1 not in self.sorted_count_map: self.sorted_count_map[count + 1] = DoubleLinkedList() self.sorted_count_map[count + 1].add(node) return self.value_map[key].value cpp int get(int key) { if (valueMap.find(key) == valueMap.end() || size == 0) { return -1; } Node* nodeToRemove = valueMap_[key]; Node* node = new Node(key, nodeToRemove->value); int count = countMap_[key]; sortedCountMap_[count]->remove(nodeToRemove); removeEntryFromSortedCountMapIfListIsEmpty(count); valueMap_.erase(key); countMap_.erase(key); valueMap_[key] = node; countMap_[key] = count + 1; if (sortedCountMap_.find(count + 1) == sortedCountMap_.end()) { sortedCountMap_[count + 1] = new DoubleLinkedList(); } sortedCountMap_[count + 1]->add(node); return valueMap_[key]->value; } csharp public int Get(int key) { if (!valueMap.ContainsKey(key) || size == 0) { return -1; } Node nodeToRemove = valueMap[key]; Node node = new Node(key, nodeToRemove.value); int count = countMap[key]; sortedCountMap[count].Remove(nodeToRemove); RemoveEntryFromSortedCountMapIfListIsEmpty(count); valueMap.Remove(key); countMap.Remove(key); valueMap[key] = node; countMap[key] = count + 1; if (!sortedCountMap.ContainsKey(count + 1)) { sortedCountMap[count + 1] = new DoubleLinkedList(); } sortedCountMap[count + 1].Add(node); return valueMap[key].value; } go func (cache *LRU_Cache) Get(key int) int { if _, ok := cache.valueMap[key]; !ok || cache.size == 0 { return -1 } nodeToRemove := cache.valueMap[key] node := &Node{key, nodeToRemove.value} count := cache.countMap[key] cache.sortedCountMap[count].remove(nodeToRemove) cache.removeEntryFromSortedCountMapIfListIsEmpty(count) delete(cache.valueMap, key) delete(cache.countMap, key) cache.valueMap[key] = node cache.countMap[key] = count + 1 if _, ok := cache.sortedCountMap[count+1]; !ok { cache.sortedCountMap[count+1] = new(DoubleLinkedList) } cache.sortedCountMap[count+1].add(node) return cache.valueMap[key].value } Finally, let's have a look at how a new element can be inserted, or existing can be updated: ```java public void put(int key, int value) { if (!valueMap.containsKey(key) && size > 0) {

    Node node = new Node(key, value);
    if (valueMap.size() == size) {
        int lowestFrequency = sortedCountMap.firstKey();
        Node nodeToRemove = sortedCountMap.get(lowestFrequency).getHead();
            sortedCountMap.get(lowestFrequency).remove(nodeToRemove);
            removeEntryFromSortedCountMapIfListIsEmpty(lowestFrequency);

        int keyToRemove = nodeToRemove.getKey();
        valueMap.remove(keyToRemove);
        countMap.remove(keyToRemove);
    }
    sortedCountMap.computeIfAbsent(1, k -> new DoubleLinkedList()).add(node);
    valueMap.put(key, node);
    countMap.put(key, 1);

} else if (valueMap.containsKey(key) && size > 0) {
    Node node = new Node(key, value);
    Node nodeToRemove = valueMap.get(key);
    int count = countMap.get(key);
    sortedCountMap.get(count).remove(nodeToRemove);
    removeEntryFromSortedCountMapIfListIsEmpty(count);
    valueMap.remove(key);
    countMap.remove(key);
    valueMap.put(key, node);
    countMap.put(key, count + 1);
    sortedCountMap.computeIfAbsent(count + 1, k -> new DoubleLinkedList()).add(node);

}

} javascript put(key, value) { if (valueMap.has(key) == false && size > 0) {

    var node = new Node(key, value);
    if (valueMap.size() == size) {
        var lowestFrequency = Math.min(...sortedCountMap.keys());
        var nodeToRemove = sortedCountMap.get(lowestFrequency).getHead();
            sortedCountMap.get(lowestFrequency).remove(nodeToRemove);
            removeEntryFromSortedCountMapIfListIsEmpty(lowestFrequency);

        var keyToRemove = nodeToRemove.getKey();
        valueMap.delete(keyToRemove);
        countMap.delete(keyToRemove);
    }
    sortedCountMap.set(1, (sortedCountMap.get(1) || new DoubleLinkedList())).add(node);
    valueMap.set(key, node);
    countMap.set(key, 1);

} else if (valueMap.has(key) && size > 0) {
    var node = new Node(key, value);
    var nodeToRemove = valueMap.get(key);
    var count = countMap.get(key);
    sortedCountMap.get(count).remove(nodeToRemove);
    removeEntryFromSortedCountMapIfListIsEmpty(count);
    valueMap.delete(key);
    countMap.delete(key);
    valueMap.set(key, node);
    countMap.set(key, count + 1);
    sortedCountMap.set(count + 1, (sortedCountMap.get(count + 1) || new DoubleLinkedList())).add(node);

}

} python def put(self, key, value): if key not in self.valueMap and self.size > 0:

    node = Node(key, value)
    if len(self.valueMap) == self.size:
        lowestFrequency = min(self.sortedCountMap.keys())
        nodeToRemove = self.sortedCountMap[lowestFrequency].getHead()
            self.sortedCountMap[lowestFrequency].remove(nodeToRemove)
            self.removeEntryFromSortedCountMapIfListIsEmpty(lowestFrequency)

        keyToRemove = nodeToRemove.getKey()
        del self.valueMap[keyToRemove]
        del self.countMap[keyToRemove]
    self.sortedCountMap.setdefault(1, DoubleLinkedList()).add(node)
    self.valueMap[key] = node
    self.countMap[key] = 1

elif key in self.valueMap and self.size > 0:
    node = Node(key, value)
    nodeToRemove = self.valueMap[key]
    count = self.countMap[key]
    self.sortedCountMap[count].remove(nodeToRemove)
    self.removeEntryFromSortedCountMapIfListIsEmpty(count)
    del self.valueMap[key]
    del self.countMap[key]
    self.valueMap[key] = node
    self.countMap[key] = count + 1
    self.sortedCountMap.setdefault(count + 1, DoubleLinkedList()).add(node)

```cpp
void put(int key, int value) {
    if (valueMap.find(key) == valueMap.end() && size > 0) {

        Node* node = new Node(key, value);
        if (valueMap.size() == size) {
            int lowestFrequency = *sortedCountMap.begin();
            Node* nodeToRemove = sortedCountMap[lowestFrequency]->getHead();
                sortedCountMap[lowestFrequency]->remove(nodeToRemove);
                removeEntryFromSortedCountMapIfListIsEmpty(lowestFrequency);

            int keyToRemove = nodeToRemove->getKey();
            valueMap.erase(keyToRemove);
            countMap.erase(keyToRemove);
        }
        sortedCountMap[1] = sortedCountMap[1] ? sortedCountMap[1] : new DoubleLinkedList();
        sortedCountMap[1]->add(node);
        valueMap[key] = node;
        countMap[key] = 1;

    } else if (valueMap.find(key) != valueMap.end() && size > 0) {
        Node* node = new Node(key, value);
        Node* nodeToRemove = valueMap[key];
        int count = countMap[key];
        sortedCountMap[count]->remove(nodeToRemove);
        removeEntryFromSortedCountMapIfListIsEmpty(count);
        valueMap.erase(key);
        countMap.erase(key);
        valueMap[key] = node;
        countMap[key] = count + 1;
        sortedCountMap[count + 1] = sortedCountMap[count + 1] ? sortedCountMap[count + 1] : new DoubleLinkedList();
        sortedCountMap[count + 1]->add(node);

    }
}

void Put(int key, int value) {
    if (!valueMap.ContainsKey(key) && size > 0) {

        Node node = new Node(key, value);
        if (valueMap.Count == size) {
            int lowestFrequency = sortedCountMap.Keys.Min();
            Node nodeToRemove = sortedCountMap[lowestFrequency].GetHead();
                sortedCountMap[lowestFrequency].Remove(nodeToRemove);
                RemoveEntryFromSortedCountMapIfListIsEmpty(lowestFrequency);

            int keyToRemove = nodeToRemove.GetKey();
            valueMap.Remove(keyToRemove);
            countMap.Remove(keyToRemove);
        }
        if (!sortedCountMap.ContainsKey(1))
        sortedCountMap[1] = new DoubleLinkedList();
        sortedCountMap[1].Add(node);
        valueMap.Add(key, node);
        countMap.Add(key, 1);

    } else if (valueMap.ContainsKey(key) && size > 0) {
        Node node = new Node(key, value);
        Node nodeToRemove = valueMap[key];
        int count = countMap[key];
        sortedCountMap[count].Remove(nodeToRemove);
        RemoveEntryFromSortedCountMapIfListIsEmpty(count);
        valueMap.Remove(key);
        countMap.Remove(key);
        valueMap.Add(key, node);
        countMap.Add(key, count + 1);
        if(!sortedCountMap.ContainsKey(count + 1))
            sortedCountMap[count + 1] = new DoubleLinkedList();
        sortedCountMap[count + 1].Add(node);

    }
}

func (self *LFUCache) Put(key int, value int) {
    if _, ok := self.valueMap[key]; !ok && self.size > 0 {

        node := Node{key: key, value: value}
        if len(self.valueMap) == self.size {
            lowestFrequency := minKey(self.sortedCountMap)
            nodeToRemove := self.sortedCountMap[lowestFrequency].GetHead()
            self.sortedCountMap[lowestFrequency].Remove(nodeToRemove)
            removeEntryFromSortedCountMapIfListIsEmpty(lowestFrequency)

            keyToRemove := nodeToRemove.getKey()
            delete(self.valueMap,keyToRemove)
            delete(self.countMap,keyToRemove)
        }
        self.sortedCountMap[1] = append(self.sortedCountMap[1], &node)
        self.valueMap[key] = &node
        self.countMap[key] = 1

    } else if _, ok := self.valueMap[key]; ok && self.size > 0 {
        node := Node{key: key, value: value}
        nodeToRemove := self.valueMap[key]
        count := self.countMap[key]
        remove(nodeToRemove, self.sortedCountMap[count])
        removeEntryFromSortedCountMapIfListIsEmpty(count)
        delete(self.valueMap,key)
        delete(self.countMap,key)
        self.valueMap[key] = &node
        self.countMap[key] = count + 1
        self.sortedCountMap[count + 1] = append(self.sortedCountMap[count + 1], &node)

    }
}

To find the element that has been least recently accessed with the lowest frequency takes O(n) time in Singly Linked List.

Conclusion

In this tutorial, we learned to implement an LFU cache using HashMap, Singly Linked List, and Doubly Linked List.

One Pager Cheat Sheet

• An overview of LFU caching and its various implementations will be discussed in this tutorial.
• The LFU Cache algorithm measures frequency and replaces the block with least frequency when the cache is full.
• LFU Cache evicts blocks based on frequency, regardless of recent access, while LRU Cache evicts blocks based on least recent access.
• Design a data structure for an LFU Cache with operations to put and get values, and a constructor to set the initial capacity which also handles replacing the least frequently used and least recently used keys when full.
• The LFU cache evicts the least frequently used memory block, regardless of when it was last accessed, by keeping track of access counters for each key.
• Implementing an LFU Cache using HashMap with O(1) access time and O(n) time to replace entries in a full cache.
• The main advantage of a HashMap is that it provides constant time access to items, regardless of the size of the map.
• We can implement an LFU Cache using a Singly Linked List, which will allow us to access the element that has been least recently used in O(1) time, but the worst complexity for updating will be O(n).
• We can implement an LFU Cache using a Doubly Linked List, taking O(1) time for insertions/updates and lookups.
• It is much more efficient to use a Doubly Linked List to locate the least recently accessed entry with the lowest frequency in O(1) time, as opposed to a Singly Linked List that requires O(n) time.
• We implemented an LFU cache using HashMap, Singly Linked List, and Doubly Linked List.