LFU Cache

In this approach, we will create 2 lists ‘cache’ and ‘nodes’, one for the keys current present in the cache and another list for the information about the key such as frequency, recency and value. Then for each query, we find the key in ‘cache’ and update the value if needed.

We will create a class Node(value, index, freq), where value is the value of the node, index int recency of the node, i.e., how recently it is used, and freq is the frequency of the Node.

Algorithm:

• In the constructor(capacity) function:
  • Set capacity as ‘capacity,
  • Initialize an array ‘cache’ of ‘capacity’ size
  • Initialize an array of Nodes(0, 0, 0) of ‘capacity’ size called ‘nodes’
  • Set currSize as 0
  • Set position as 0
• In the get(key) function:
  • Increase position by 1
  • Set value as -1
  • Iterate i from 0 to ‘capacity - 1’
    • If key is equal to cache[i]
      • Set value as nodes[i].value
      • Set nodes[i].index as position
      • Increase nodes[i].freq by 1
  • Return value
• In the put(key, value) function
  • Increase position by 1
  • If capacity is 0 return
  • Iterate i from 0 to ‘capacity - 1’
    • If key is equal to cache[i]
      • Set nodes[i].value as value 
      • Set nodes[i].index as position
      • Increase nodes[i].freq by 1
      • Return from the function
  • If currSize is less than capacity
    • Set cache[currSize] as key
    • Set nodes[currSize]’s value, index and freq as value, position, 1 respectively
    • Increase currSize by 1
  • Otherwise,
    • Find the node in the nodes array with minimum ‘freq’ and if the frequency is equal get the one with the minimum position. Set it as pos.
    • Set cache[pos] as key
    • Set nodes[pos]’s value, index and freq as value, position, 1 respectively

In this approach, we create a hash map of ordered maps, where each key in the map will have a set of the node with that frequency. Each time node is fetched or updated, we update the frequency of the node by deleting it from its ordered map and adding it in the ordered map with 1 higher frequency.

We also maintain a minimum frequency, if the cache is full we can delete the first element in the map of minimum frequency, since each map is ordered it will be the first element of the map.

In an ordered map deletion will take logarithmic time.

We create a Node(value) class, where ‘value’ is the value of the node and it also has a frequency property ‘freq’ which is initialized to 1.
 

We will also create a helper method in the LFUCache class called updateNodeFreq(key), where the key is the key of the node whose frequency is to be updated.

Algorithm:

• In the constructor(capacity) function:
  • Set capacity as ‘capacity,
  • Initialise a hashmap of an integer as key and ordered map as the value called countNode
  • Initialise a hashmap of an integer key and Node as value called  keyNode
  • Set minCount as 0
• In the function updateNodeFreq(key):
  • Set freq as keyNode[key].freq
  • Delete key from the ordered map ‘countNode[freq]’
  • Increase keyNode[key].freq by 1
  • Set countNode[freq + 1][key] as keyNode[key].
  • If the length of the map countNode[minCount] is 0
    • Increase minCount by 1
• In the get(key) function
  • If key is not in keyNode return -1
  • Set value as keyNode[key].value
  • Call updateNodeFreq(key)
  • Return value
• Int the put(key, value)
  • If capacity is 0 return
  • If key is in keyNode
    • Set keyNode[key].value as value
    • Call updateNodeFreq(key)
    • Return from the function
  • If size of keyNode is equal to capacity
    • Pop the first item in coutNode[minCount] as set it’s key as minKey
    • Delete minKey from keyNode
  • Set keyNode[key] equal to a new instance of Node(value)
  • Set countNode[1][key] as keyNode[key]
  • Set minCount as 1

In this approach, we will make a hashmap of all frequencies, but instead of storing the nodes in an ordered map, we will store them in a doubly-linked list. Due to using a doubly-linked list, if we have a reference for a node we can delete it in constant time.

We will create a Node(key, value), where key and value are the respective values in the cache. It also has prev and next, the pointer not next, and previous nodes in the linked list.

We will create a class DoubleLinkedList, which has properties like rootNode a Node object, representing the sentinel node of the linked list. rootNode.prev will point to the last node of the list, while rootNode.next will point to the first node of the list.

We will create a method in LFUCache class updateNodeFreq(node), where node a Node class object whose frequency is to be updated.

In this approach, we will make a hashmap of all frequencies, but instead of storing the nodes in an ordered map, we will store them in a doubly-linked list. Due to using a doubly-linked list, if we have a reference for a node we can delete it in constant time.

We will create a Node(key, value), where key and value are the respective values in the cache. It also has prev and next, the pointer not next, and previous nodes in the linked list.

We will create a class DoubleLinkedList, which has properties like rootNode a Node object, representing the sentinel node of the linked list. rootNode.prev will point to the last node of the list, while rootNode.next will point to the first node of the list.

We will create a method in LFUCache class updateNodeFreq(node), where node a Node class object whose frequency is to be updated.

Algorithm:

• In the class DoubleLinkedList, 
  • constructor():
    • Set rootNode as Node(0, 0)
    • Set rootNode.next and rootNode.prev as rootNode
    • Set currentSize  as 0
  • In the pop(node) method:
    • If currentSize is 0 return
    • If node is null set node as rootNode.prev
    • Set node.prev.next as node.next
    • Set node.next.prev as node.prev
    • Decrease currentSize by 1
    • Return node
  • In the append(node) method:
    • Set node.next as rootNode.next
    • Set node.prev as rootNode
    • Set node.next.prev as node
    • Set rootNode.next as node
    • Increase currentSize by 1
• In the class LFUCache:
  • In the constructor(capacity):
    • Set currentSize as 0
    • Set capacity as capacity 
    • Initialise an empty hashmap of nodes nodeMap
    • Initialise an empty hashmap of DoubleLinkedList freqMap
    • Set minFreq as 0
  • In the function updateNodeFreq(node)
    • Set freq as node.freq
    • Call freqMap[freq].pop(node)
    • If minFreq is equal to freq and freqMap[freq] is empty
      • Then increase minFreq by 1
    • Increase node.freq by 1
    • Set freq as node.freq
    • Insert node in freqMap[freq]
  • Int the function get(key) function:
    • If key is not in nodeMap, return -1
    • Set node as nodeMap[key]
    • Call updateNodeFreq(node)
    • Return node.value
  • In the put(key, value) function
    • If capacity is 0 return
    • If key is in nodeMap
      • Set node as nodeMap[key]
      • Call updateNodeFreq(node)
      • Set node.value as value
      • Return
    • If currentSize is equal to capacity:
      • Set node as nodeMap[minFreq].pop()
      • Delete nodeMap[node.key]
      • Decrease currentSize by 1
    • Set node as Node(key, value)
    • Set nodeMap[key] as node
    • Call freqMap[1].append(node)
    • Set minFreq as 1
    • Increase currSize by 1