LFU Cache

Pre Requisites: LRU Cache

Intuition:

As the name suggests, the data items (key-value pairs) that are least frequently used will be removed from the cache memory. To mark the data items as recently used, a doubly linked list can be used. The most recently used data item will be placed in the front and the least recently used data item will be placed at the end of the doubly linked list.

Why using a Doubly Linked List?

Because doubly linked list data structure makes the insertion and deletion operation on data items in constant time while making sure the order of data items remains.

But in order to implement the get method for LFU cache, the searching operation will take linear time where each data-item needs to be checked. To improve the complexity of get method, a hashmap can be used to store the key and the address of node containing the key (if it exists).

Also, to store the frequencies of different data-items. A Hashmap can be used to store the lists of data-items based on their frequenices.
This way, the two methods can be implemented in constant time:

Get method: Using hashmap, it can be found whether a key exists in the doubly linked list. If it exists, the corresponding value can be returned using the address of node, otherwise, -1 can be returned.
Put method: If the key exists in the doubly linked list, its value can be updated. Otherwise, if the cache limit is reached, the least frequently used data-item can be removed and the current key-value pair can be inserted.

Approach:

The cache is initialized with a specified capacity. Dummy head and tail nodes are created for each list to simplify edge case handling.
Updating Frequency:
- When a node is accessed or updated, it is removed from its current frequency list.
- If this node was the only node with the minimum frequency, the minimum frequency is incremented.
- The node's frequency is incremented, and it is added to the front of the list corresponding to the new frequency.
- Both hash maps are updated to reflect these changes.
Get Operation:
- Check if the key exists in the keyNode map.
- If present, retrieve the node, update its frequency, and return its value. If not present, return -1.
Put Operation:
- Check if the key already exists in the keyNode map.
- If present, update the node's value, update its frequency, and return. If not present, check if the cache has reached its maximum capacity.
- If at capacity, remove the least frequently used node (the node in the list with the minimum frequency and the least recent usage).
- Create a new node for the key-value pair, set its frequency to 1, and add it to the front of the frequency list for nodes with frequency 1. Update both hash maps to reflect the addition of the new node.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

/* To implement a node in doubly linked 
list that will store data items */
struct Node {
   int key, value, cnt;
   Node *next; 
   Node *prev;
   Node(int _key, int _value) {
       key = _key;
       value = _value; 
       cnt = 1; 
   }
}; 

// To implement the doubly linked list
struct List {
   int size; // Size 
   Node *head; // Dummy head
   Node *tail; // Dummy tail
   
   // Constructor
   List() {
       head = new Node(0, 0); 
       tail = new Node(0,0); 
       head->next = tail;
       tail->prev = head; 
       size = 0;
   }
   
   // Function to add node in front 
   void addFront(Node *node) {
       Node* temp = head->next;
       node->next = temp;
       node->prev = head;
       head->next = node;
       temp->prev = node;
       size++; 
   }
   
   // Function to remove node from the list
   void removeNode(Node* delnode) {
       Node* prevNode = delnode->prev;
       Node* nextNode = delnode->next;
       prevNode->next = nextNode;
       nextNode->prev = prevNode;
       size--; 
   }
};

// Class to implement LFU cache
class LFUCache {
private:

   // Hashmap to store the key-nodes pairs
   map<int, Node*> keyNode; 
   
   /* Hashmap to maintain the lists 
   having different frequencies */
   map<int, List*> freqListMap; 
   
   int maxSizeCache; // Max size of cache
   
   /* To store the frequency of least 
   frequently used data-item */
   int minFreq; 
   
   // To store current size of cache
   int curSize; 
   
public:

   // Constructor
   LFUCache(int capacity) {
       // Set the capacity
       maxSizeCache = capacity; 
       minFreq = 0; // Set minimum frequency
       curSize = 0; // Set current frequency
   }
   
   // Method to update frequency of data-items
   void updateFreqListMap(Node *node) {
       
       // Remove from Hashmap
       keyNode.erase(node->key); 
       
       // Update the frequency list hashmap
       freqListMap[node->cnt]->removeNode(node); 
       
       // If node was the last node having it's frequency
       if(node->cnt == minFreq && 
          freqListMap[node->cnt]->size == 0) {
              
           // Update the minimum frequency
           minFreq++; 
       }
       
       // Creating a dummy list for next higher frequency
       List* nextHigherFreqList = new List();
       
       // If the next higher frequency list already exists
       if(freqListMap.find(node->cnt + 1) != 
          freqListMap.end()) {
              
           // Update pointer to already existing list
           nextHigherFreqList = freqListMap[node->cnt + 1];
       } 
       
       // Increment the count of data-item
       node->cnt += 1; 
       
       // Add the node in front of higher frequency list
       nextHigherFreqList->addFront(node); 
       
       // Update the 
       freqListMap[node->cnt] = nextHigherFreqList; 
       keyNode[node->key] = node;
   }
   
   // Method to get the value of key from LFU cache
   int get(int key) {
       
       // Return the value if key exists
       if(keyNode.find(key) != keyNode.end()) {
           Node* node = keyNode[key]; // Get the node
           int val = node->value; // Get the value
           updateFreqListMap(node); // Update the frequency
           
           // Return the value
           return val; 
       }
       
       // Return -1 if key is not found
       return -1; 
   }
   
   void put(int key, int value) {
       /* If the size of Cache is 0, 
       no data-items can be inserted */
       if (maxSizeCache == 0) {
           return;
       }
       
       // If key already exists
       if(keyNode.find(key) != keyNode.end()) {
           
           // Get the node
           Node* node = keyNode[key]; 
           
           // Update the value
           node->value = value; 
           
           // Update the frequency
           updateFreqListMap(node); 
       }
       
       // Else if the key does not exist
       else {
           
           // If cache limit is reached
           if(curSize == maxSizeCache) {
               
               // Remove the least frequently used data-item
               List* list = freqListMap[minFreq]; 
               keyNode.erase(list->tail->prev->key); 
               
               // Update the frequency map 
               freqListMap[minFreq]->removeNode(
                   list->tail->prev
               );
               
               // Decrement the current size of cache
               curSize--; 
           }
           
           // Increment the current cache size
           curSize++; 
           
           // Adding new value to the cache
           minFreq = 1; // Set its frequency to 1
           
           // Create a dummy list
           List* listFreq = new List(); 
           
           // If the list already exist
           if(freqListMap.find(minFreq) != 
              freqListMap.end()) {
               
               // Update the pointer to already present list
               listFreq = freqListMap[minFreq]; 
           }
           
           // Create the node to store data-item
           Node* node = new Node(key, value); 
           
           // Add the node to dummy list
           listFreq->addFront(node);
           
           // Add the node to Hashmap
           keyNode[key] = node; 
           
           // Update the frequency list map 
           freqListMap[minFreq] = listFreq; 
       }
   }
};

int main() {
  // LFU Cache
  LFUCache cache(2);

  // Queries
  cache.put(1, 1);
  cache.put(2, 2);
  cout << cache.get(1) << " ";
  cache.put(3, 3);
  cout << cache.get(2) << " ";
  cout << cache.get(3) << " ";
  cache.put(4, 4);
  cout << cache.get(1) << " ";
  cout << cache.get(3) << " ";
  cout << cache.get(4) << " ";

  return 0;
}
import java.util.HashMap;
import java.util.Map;

/* To implement a node in doubly linked 
list that will store data items */
class Node {
   int key, value, cnt;
   Node next;
   Node prev;
   Node(int _key, int _value) {
       key = _key;
       value = _value;
       cnt = 1;
   }
}

// To implement the doubly linked list
class List {
   int size; // Size 
   Node head; // Dummy head
   Node tail; // Dummy tail
   
   // Constructor
   List() {
       head = new Node(0, 0);
       tail = new Node(0, 0);
       head.next = tail;
       tail.prev = head;
       size = 0;
   }
   
   // Function to add node in front 
   void addFront(Node node) {
       Node temp = head.next;
       node.next = temp;
       node.prev = head;
       head.next = node;
       temp.prev = node;
       size++;
   }
   
   // Function to remove node from the list
   void removeNode(Node delnode) {
       Node prevNode = delnode.prev;
       Node nextNode = delnode.next;
       prevNode.next = nextNode;
       nextNode.prev = prevNode;
       size--;
   }
}

// Class to implement LFU cache
class LFUCache {
   // Hashmap to store the key-nodes pairs
   private Map<Integer, Node> keyNode;
   
   /* Hashmap to maintain the lists 
   having different frequencies */
   private Map<Integer, List> freqListMap;
   
   private int maxSizeCache; // Max size of cache
   
   /* To store the frequency of least 
   frequently used data-item */
   private int minFreq;
   
   // To store current size of cache
   private int curSize;
   
   // Constructor
   public LFUCache(int capacity) {
       // Set the capacity
       maxSizeCache = capacity;
       minFreq = 0; // Set minimum frequency
       curSize = 0; // Set current frequency
       keyNode = new HashMap<>();
       freqListMap = new HashMap<>();
   }
   
   // Method to update frequency of data-items
   private void updateFreqListMap(Node node) {
       // Remove from Hashmap
       keyNode.remove(node.key);
       
       // Update the frequency list hashmap
       freqListMap.get(node.cnt).removeNode(node);
       
       // If node was the last node having its frequency
       if (node.cnt == minFreq && 
           freqListMap.get(node.cnt).size == 0) {
           // Update the minimum frequency
           minFreq++;
       }
       
       // Creating a dummy list for next higher frequency
       List nextHigherFreqList = new List();
       
       // If the next higher frequency list already exists
       if (freqListMap.containsKey(node.cnt + 1)) {
           // Update pointer to already existing list
           nextHigherFreqList = 
               freqListMap.get(node.cnt + 1);
       }
       
       // Increment the count of data-item
       node.cnt += 1;
       
       // Add the node in front of higher frequency list
       nextHigherFreqList.addFront(node);
       
       // Update the frequency list map
       freqListMap.put(node.cnt, nextHigherFreqList);
       keyNode.put(node.key, node);
   }
   
   // Method to get the value of key from LFU cache
   public int get(int key) {
       // Return the value if key exists
       if (keyNode.containsKey(key)) {
           Node node = keyNode.get(key); // Get the node
           int val = node.value; // Get the value
           updateFreqListMap(node); // Update the frequency
           // Return the value
           return val;
       }
       // Return -1 if key is not found
       return -1;
   }
   
   public void put(int key, int value) {
       /* If the size of Cache is 0, 
       no data-items can be inserted */
       if (maxSizeCache == 0) {
           return;
       }
       
       // If key already exists
       if (keyNode.containsKey(key)) {
           // Get the node
           Node node = keyNode.get(key);
           // Update the value
           node.value = value;
           // Update the frequency
           updateFreqListMap(node);
       } else {
           // If cache limit is reached
           if (curSize == maxSizeCache) {
               // Remove the least frequently used data-item
               List list = freqListMap.get(minFreq);
               keyNode.remove(list.tail.prev.key);
               
               // Update the frequency map
               freqListMap.get(minFreq).removeNode(list.tail.prev);
               // Decrement the current size of cache
               curSize--;
           }
           // Increment the current cache size
           curSize++;
           
           // Adding new value to the cache
           minFreq = 1; // Set its frequency to 1
           
           // Create a dummy list
           List listFreq = new List();
           
           // If the list already exists
           if (freqListMap.containsKey(minFreq)) {
               // Update the pointer to already present list
               listFreq = freqListMap.get(minFreq);
           }
           
           // Create the node to store data-item
           Node node = new Node(key, value);
           
           // Add the node to dummy list
           listFreq.addFront(node);
           
           // Add the node to Hashmap
           keyNode.put(key, node);
           
           // Update the frequency list map
           freqListMap.put(minFreq, listFreq);
       }
   }
   
   public static void main(String[] args) {
       // LFU Cache
       LFUCache cache = new LFUCache(2);
       
       // Queries
       cache.put(1, 1);
       cache.put(2, 2);
       System.out.print(cache.get(1) + " ");
       cache.put(3, 3);
       System.out.print(cache.get(2) + " ");
       System.out.print(cache.get(3) + " ");
       cache.put(4, 4);
       System.out.print(cache.get(1) + " ");
       System.out.print(cache.get(3) + " ");
       System.out.print(cache.get(4) + " ");
   }
}
# To implement a node in doubly linked 
# list that will store data items
class Node:
   def __init__(self, _key, _value):
       self.key = _key
       self.value = _value
       self.cnt = 1
       self.next = None
       self.prev = None

# To implement the doubly linked list
class List:
   def __init__(self):
       self.size = 0  # Size 
       self.head = Node(0, 0)  # Dummy head
       self.tail = Node(0, 0)  # Dummy tail
       self.head.next = self.tail
       self.tail.prev = self.head

   # Function to add node in front 
   def addFront(self, node):
       temp = self.head.next
       node.next = temp
       node.prev = self.head
       self.head.next = node
       temp.prev = node
       self.size += 1

   # Function to remove node from the list
   def removeNode(self, delnode):
       prevNode = delnode.prev
       nextNode = delnode.next
       prevNode.next = nextNode
       nextNode.prev = prevNode
       self.size -= 1

# Class to implement LFU cache
class LFUCache:
   def __init__(self, capacity):
       # Set the capacity
       self.maxSizeCache = capacity
       self.minFreq = 0  # Set minimum frequency
       self.curSize = 0  # Set current frequency
       
       # Hashmap to store the key-nodes pairs
       self.keyNode = {}  
       
       # Hashmap to maintain the lists 
       # having different frequencies
       self.freqListMap = {}

   # Method to update frequency of data-items
   def updateFreqListMap(self, node):
       # Remove from Hashmap
       del self.keyNode[node.key]
       
       # Update the frequency list hashmap
       self.freqListMap[node.cnt].removeNode(node)
       
       # If node was the last node having its frequency
       if (node.cnt == self.minFreq and 
           self.freqListMap[node.cnt].size == 0):
               
           # Update the minimum frequency
           self.minFreq += 1
       
       # Creating a dummy list for next higher frequency
       nextHigherFreqList = List()
       
       # If the next higher frequency list already exists
       if node.cnt + 1 in self.freqListMap:
           
           # Update pointer to already existing list
           nextHigherFreqList = self.freqListMap[node.cnt + 1]
       
       # Increment the count of data-item
       node.cnt += 1
       
       # Add the node in front of higher frequency list
       nextHigherFreqList.addFront(node)
       
       # Update the frequency list map
       self.freqListMap[node.cnt] = nextHigherFreqList
       self.keyNode[node.key] = node

   # Method to get the value of key from LFU cache
   def get(self, key):
       # Return the value if key exists
       if key in self.keyNode:
           node = self.keyNode[key]  # Get the node
           val = node.value  # Get the value
           self.updateFreqListMap(node)  # Update the frequency
           # Return the value
           return val
           
       # Return -1 if key is not found
       return -1

   def put(self, key, value):
       
       # If the size of Cache is 0, 
       # no data-items can be inserted
       if self.maxSizeCache == 0:
           return
       
       # If key already exists
       if key in self.keyNode:
           node = self.keyNode[key]  # Get the node
           node.value = value  # Update the value
           self.updateFreqListMap(node)  # Update the frequency
       else:
           # If cache limit is reached
           if self.curSize == self.maxSizeCache:
               # Remove the least frequently used data-item
               list = self.freqListMap[self.minFreq]
               del self.keyNode[list.tail.prev.key]
               # Update the frequency map
               self.freqListMap[self.minFreq].removeNode(list.tail.prev)
               self.curSize -= 1  # Decrement the current size of cache
           
           self.curSize += 1  # Increment the current cache size
           # Adding new value to the cache, 
           # set its frequency to 1
           self.minFreq = 1  
           
           # Create a dummy list
           listFreq = List()
           
           # If the list already exists
           if self.minFreq in self.freqListMap:
               
               # Update the pointer to already present list
               listFreq = self.freqListMap[self.minFreq]
           
           # Create the node to store data-item
           node = Node(key, value)
           
           # Add the node to dummy list
           listFreq.addFront(node)
           
           # Add the node to Hashmap
           self.keyNode[key] = node
           
           # Update the frequency list map
           self.freqListMap[self.minFreq] = listFreq

# LFU Cache
cache = LFUCache(2)

# Queries
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1), end=" ")
cache.put(3, 3)
print(cache.get(2), end=" ")
print(cache.get(3), end=" ")
cache.put(4, 4)
print(cache.get(1), end=" ")
print(cache.get(3), end=" ")
print(cache.get(4), end=" ")
/* To implement a node in doubly linked 
list that will store data items */
class Node {
   constructor(_key, _value) {
       this.key = _key;
       this.value = _value;
       this.cnt = 1;
       this.next = null;
       this.prev = null;
   }
}

// To implement the doubly linked list
class List {
   constructor() {
       this.size = 0; // Size 
       this.head = new Node(0, 0); // Dummy head
       this.tail = new Node(0, 0); // Dummy tail
       this.head.next = this.tail;
       this.tail.prev = this.head;
   }
   
   // Function to add node in front 
   addFront(node) {
       let temp = this.head.next;
       node.next = temp;
       node.prev = this.head;
       this.head.next = node;
       temp.prev = node;
       this.size++;
   }
   
   // Function to remove node from the list
   removeNode(delnode) {
       let prevNode = delnode.prev;
       let nextNode = delnode.next;
       prevNode.next = nextNode;
       nextNode.prev = prevNode;
       this.size--;
   }
}

// Class to implement LFU cache
class LFUCache {
   constructor(capacity) {
       // Set the capacity
       this.maxSizeCache = capacity;
       this.minFreq = 0; // Set minimum frequency
       this.curSize = 0; // Set current frequency
       
       // Hashmap to store the key-nodes pairs
       this.keyNode = new Map(); 
       
       /* Hashmap to maintain the lists 
       having different frequencies */
       this.freqListMap = new Map(); 
   }
   
   // Method to update frequency of data-items
   updateFreqListMap(node) {
       // Remove from Hashmap
       this.keyNode.delete(node.key);
       
       // Update the frequency list hashmap
       this.freqListMap.get(node.cnt).removeNode(node);
       
       // If node was the last node having its frequency
       if (node.cnt === this.minFreq && 
           this.freqListMap.get(node.cnt).size === 0) {
           // Update the minimum frequency
           this.minFreq++;
       }
       
       // Creating a dummy list for next higher frequency
       let nextHigherFreqList = new List();
       
       // If the next higher frequency list already exists
       if (this.freqListMap.has(node.cnt + 1)) {
           
           // Update pointer to already existing list
           nextHigherFreqList = 
               this.freqListMap.get(node.cnt + 1);
       }
       
       // Increment the count of data-item
       node.cnt += 1;
       
       // Add the node in front of higher frequency list
       nextHigherFreqList.addFront(node);
       
       // Update the frequency list map
       this.freqListMap.set(node.cnt, nextHigherFreqList);
       this.keyNode.set(node.key, node);
   }
   
   // Method to get the value of key from LFU cache
   get(key) {
       // Return the value if key exists
       if (this.keyNode.has(key)) {
           let node = this.keyNode.get(key); // Get the node
           let val = node.value; // Get the value
           this.updateFreqListMap(node); // Update the frequency
           // Return the value
           return val;
       }
       // Return -1 if key is not found
       return -1;
   }
   
   put(key, value) {
       /* If the size of Cache is 0, 
       no data-items can be inserted */
       if (this.maxSizeCache === 0) {
           return;
       }
       
       // If key already exists
       if (this.keyNode.has(key)) {
           let node = this.keyNode.get(key); // Get the node
           node.value = value; // Update the value
           this.updateFreqListMap(node); // Update the frequency
       } else {
           // If cache limit is reached
           if (this.curSize === this.maxSizeCache) {
               // Remove the least frequently used data-item
               let list = this.freqListMap.get(this.minFreq);
               this.keyNode.delete(list.tail.prev.key);
               // Update the frequency map
               this.freqListMap.get(this.minFreq).removeNode(list.tail.prev);
               this.curSize--; // Decrement the current size of cache
           }
           this.curSize++; // Increment the current cache size
           this.minFreq = 1; // Adding new value to the cache, set its frequency to 1
           
           // Create a dummy list
           let listFreq = new List();
           
           // If the list already exists
           if (this.freqListMap.has(this.minFreq)) {
               // Update the pointer to already present list
               listFreq = this.freqListMap.get(this.minFreq);
           }
           
           // Create the node to store data-item
           let node = new Node(key, value);
           
           // Add the node to dummy list
           listFreq.addFront(node);
           
           // Add the node to Hashmap
           this.keyNode.set(key, node);
           
           // Update the frequency list map
           this.freqListMap.set(this.minFreq, listFreq);
       }
   }
}

// LFU Cache
const cache = new LFUCache(2);

// Queries
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1) + " ");
cache.put(3, 3);
console.log(cache.get(2) + " ");
console.log(cache.get(3) + " ");
cache.put(4, 4);
console.log(cache.get(1) + " ");
console.log(cache.get(3) + " ");
console.log(cache.get(4) + " ");

Complexity Analysis:

Time Complexity: O(N) (where N is the number of queries on the LFU cache)
Each get and put method takes an average of constant time making the overall complexity as O(N).

Space Complexity: O(cap) (where cap is the capacity of LFU cache defined)
At maximum the cache can store the numbers of data-items equal to its capacity taking O(cap) space.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Why using a Doubly Linked List?

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code