{"id":1634,"date":"2024-02-03T13:00:00","date_gmt":"2024-02-03T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1634"},"modified":"2024-02-05T05:19:29","modified_gmt":"2024-02-05T05:19:29","slug":"lfu-cache-problem","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/lfu-cache-problem\/","title":{"rendered":"LFU Cache Problem Solved (C++, Java, Python)"},"content":{"rendered":"\n

In data management, efficient caching mechanisms are important in enhancing system performance. One of the cache replacement policies is the Least Frequently Used algorithm. In this article, we will discuss how to solve the LFU cache problem.<\/p>\n\n\n\n

What is LFU Cache?<\/strong><\/h2>\n\n\n\n

LFU, or Least Frequently Used, is a caching strategy where the system tracks the access frequency of cached elements and discards the element with the lowest number of accesses when the cache reaches its capacity.<\/strong><\/p>\n\n\n\n

This strategy prioritizes retaining the elements that have been accessed most often in the past, optimizing cache utilization for scenarios where recently accessed elements are likely to be needed again soon.<\/p>\n\n\n\n

Let\u2019s discuss how we can implement LFU Cache.<\/p>\n\n\n\n

Using Hashing Approach<\/strong><\/h2>\n\n\n\n

The hashing Approach is used to implement LFU Cache in this we will use Three hash-maps to implement LFU Cache.<\/strong><\/p>\n\n\n\n

Below are the steps to be followed to solve this Problem:-<\/p>\n\n\n\n

    \n
  • Firstly we will declare three hashmaps \u201cfrequencyList\u201d, \u201ckeyNode\u201d and \u201cfrequency\u201d.<\/li>\n\n\n\n
  • In these hashmaps, we have key-value pairs in the following manner:\n
      \n
    • frequencyList: <\/strong>the key is an integer and the value will be a list<\/li>\n\n\n\n
    • keyNode<\/strong>: the key is an integer and the value is an iterator containing the iterator for an element of a specific frequency of frequencyList.<\/li>\n\n\n\n
    • frequency<\/strong>: key is an integer value that is a pair of two other integers containing the frequency count and the value of a particular key.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
    • We will declare Two variables ‘minFrequency’ which will hold the minimum frequency from which we need to remove the number and ‘currentSize’ which determines the size of the LFU Cache.<\/li>\n<\/ul>\n\n\n\n

      Here are the 3 functions we need to solve the problem:<\/p>\n\n\n\n

        \n
      1. LFUCache(int capacity) <\/strong>Initialize the LFU cache with positive size capacity.<\/strong><\/li>\n\n\n\n
      2. int get(int key)\u00a0<\/strong>\n
          \n
        • In LFU if the key is new. we need to return -1.<\/li>\n\n\n\n
        • If the key is not new, then we need to erase that key from the frequencyList. Also, increase the frequency count of the current element.\u00a0<\/li>\n\n\n\n
        • Now Insert them into the frequencyList.<\/li>\n\n\n\n
        • If the minFrequency list is 0, then increase minFrequency by 1.<\/li>\n\n\n\n
        • Return the corresponding value for the given key.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • void put(int key, int value)<\/strong>\n
            \n
          • If the capacity is less than 1, no put() operation will take place.<\/li>\n\n\n\n
          • Now, if the given key is a new one and we are at capacity then we need to remove the least used key.<\/li>\n\n\n\n
          • We will remove the very last element available from the frequencyList of minFrequency index. We also remove that element from frequency hashmap as well.<\/li>\n\n\n\n
          • \u00a0As the item is a new one then, the minFrequency will be set to 1. And we will add them in frequencyList’s minFrequency index, frequency, and keyNode.<\/li>\n\n\n\n
          • If the key is not new, then we need to add the value to the frequency hashmap.<\/li>\n\n\n\n
          • Then we will call the get() function.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n

            Let’s take an example:<\/p>\n\n\n\n

            Input: <\/strong><\/p>\n\n\n\n

            [\"LFUCache\", \"put\", \"put\", \"get\", \"put\", \"get\", \"get\", \"put\", \"get\", \"get\", \"get\"]\n[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]<\/code><\/pre>\n\n\n\n
            Output<\/strong>:<\/p>\n\n\n\n
            [null, null, null, 1, null, -1, 3, null, -1, 3, 4]<\/code><\/pre>\n\n\n\n
            Explanation:<\/strong><\/p>\n\n\n\n
            cnt(x) =<\/strong> the use counter for key x<\/p>\n\n\n\n
            cache=[] will show the last used order for tiebreakers (the leftmost element is the most recent)<\/p>\n\n\n\n
              \n
            • In this firstly we are declaring LFU of size 2<\/li>\n<\/ul>\n\n\n
              \n
              \"Declaring<\/figure>\n<\/div>\n\n\n
                \n
              • LFUCache.put(1,1) now cache = [1,_] and cnt(1) = 1;<\/li>\n<\/ul>\n\n\n
                \n
                \"Put<\/figure>\n<\/div>\n\n\n
                  \n
                • LFUCache.put(2,2) now cache = [2,1] and cnt(1) = 1, cnt(2) = 1<\/li>\n<\/ul>\n\n\n
                  \n
                  \"Put<\/figure>\n<\/div>\n\n\n
                    \n
                  • LFUCache.get(1) and 1 is present so we will return 1, cache=[1,2], cnt(2)=1, cnt(1)=2<\/li>\n\n\n\n
                  • LFUCache.put(3,3) now 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2. cache = [3,1] and cnt(3) = 1, cnt(1) = 2<\/li>\n<\/ul>\n\n\n
                    \n
                    \"Put<\/figure>\n<\/div>\n\n\n
                      \n
                    • LFUCache.get(2); we will return -1.<\/li>\n\n\n\n
                    • LFUCache.get(3); we will return 3. And now cache = [3,1] and cnt(3) = 2, cnt(1) = 2.<\/li>\n\n\n\n
                    • LFUCache.put(4,4) now Both 1 and 3 have the same count, but 1 is LRU, invalidate 1. Now cache=[4,3], cnt(4)=1, cnt(3)=2<\/li>\n<\/ul>\n\n\n
                      \n
                      \"Put<\/figure>\n<\/div>\n\n\n