LFU Cache (Least Frequently Used) - akshaydhule/Codes GitHub Wiki

Implementation of data structure for Least Frequently Used (LFU) cache supporting get and set operation.

Link : https://github.com/akshaydhule/Codes/blob/codes/LFU-Cache/LFUcache.cpp

  • get(key) - Gets the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
  • set(key, value) - Sets or inserts the value if the key is not already present. When the cache reaches its capacity, it invalidates the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key gets evicted.

Design:

  • Data structures :
  1. Doubly Linked list Node (Lnode) - stores value of the key and pointer to previous and next node.
  2. Hashmap for maintaining mapping of key to pointer to node which contains corresponding Lnode.
  • Doubly Linked list Node (node) - stores Frequency.
  • DLL of all keys having same frequency. In decreasing order of occurrence of keys.
  • Head pointing to most recent.
  • tail pointing to least recent of given frequency.

  • Hashmap for maintaining mapping of key and pointer to corresponding Lnode in DLL, In increasing order of frequency.

  • Main LFU class contains -

  • Current Capacity.
  • Maximum Capacity.
  • Root node points to root of node DLL.

Cases to Handle :

  • Get operation : every get operation increments the frequency of key, updates order of recent calls
  • Detach the corresponding Lnode from DLL
    • If single Lnode in root.
      • Single node.
      • Multiple nodes.
    • More than one Lnode in root.
  • Temp points to prev existing node else NULL.
  • Increment frequency of key, Attach the node.
    • if root is NULL.
    • find node of frequency + 1 and add node in Lnode DLL of that node.
    • If not present create new node of frequency and add Lnode to that node.
    • Add node in-between and at the end.
  • Set operation : Every set operation either updates the value of the key or creates new node of frequency 1.
  • If key already available, Update the value.
  • If capacity is maximum. remove least frequency, least recent Lnode.
  • if 1 Frequency node present, attach to DLL of that node.
  • Else create new node and update the node & Lnode DLL.