Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

LFU Cache

Moderate

0/80

Contributed by

31 upvotes

Asked in companies

Problem statement

Design and implement a Least Frequently Used(LFU) Cache, to implement the following functions:

1. put(U__ID, value): Insert the value in the cache if the key(‘U__ID’) is not already present or update the value of the given key if the key is already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting the new item.

2. get(U__ID): Return the value of the key(‘U__ID’),  present in the cache, if it’s present otherwise return -1.

Note:

  1) The frequency of use of an element is calculated by a number of operations with its ‘U_ID’ performed after it is inserted in the cache.

  2) If multiple elements have the least frequency then we remove the element which was least recently used.

You have been given ‘M’ operations which you need to perform in the cache. Your task is to implement all the functions of the LFU cache.

Type 1: for put(key, value) operation.
Type 2: for get(key) operation.

Example:

We perform the following operations on an empty cache which has capacity 2:

When operation 1 2 3 is performed, the element with 'U_ID' 2 and value 3 is inserted in the cache.

When operation 1 2 1 is performed, the element with 'U_ID' 2’s value is updated to 1.  

When operation 2 2 is performed then the value of 'U_ID' 2 is returned i.e. 1.

When operation 2 1 is performed then the value of 'U_ID' 1 is to be returned but it is not present in cache therefore -1 is returned.

When operation 1 1 5 is performed, the element with 'U_ID' 1 and value 5 is inserted in the cache. 

When operation 1 6 4 is performed, the cache is full so we need to delete an element. First, we check the number of times each element is used. Element with 'U_ID' 2 is used 3 times (2 times operation of type 1 and 1-time operation of type 1). Element with 'U_ID' 1 is used 1 time (1-time operation of type 1). So element with 'U_ID' 1 is deleted. The element with 'U_ID' 6 and value 4 is inserted in the cache.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains two single space-se[arated integers ‘N’ and ‘M’ representing the size of cache and number of operations respectively.

Next ‘M’ lines contain operations that have to be performed on the cache.

Output Format:

For each test case, print a vector/list that contains answers of all the operations of type 2 and in the order in which they were asked.

Note:

1. All the operations are valid. 
2. You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 1000
1 <= M <= 1000
1 <= U_ID <= 10^3
1 <= VAL<= 10^6

Time Limit: 1sec

Sample Input 1:

Sample Output 1:

-1 1
8 -1 6

Sample Output 1 Explanation:

Test case1:

Let’s say i’th operation takes place at t=i. The status after each operation is as follows.
1 4 1 - Element with 'U_ID' 4 and value 1 is inserted in the cache.
2 2 - No element with 'U_ID' 2 is present in the cache so -1 is returned.
2 4 - Element with 'U_ID' 4 is present in the cache so its value i.e 1 is returned.

Therefore the answer is -1 1.


Test case 2:

Let’s say i’th operation takes place at t=i. Status after each operation is as follows.
1 2 7 - Element with 'U_ID' 2 and value 7 is inserted in the cache.
1 1 8 - Element with 'U_ID' 1 and value 8 is inserted in the cache.
1 2 6 - Element with 'U_ID' 2 is already present in the cache so value is updated to 6.
2 1 - Element with 'U_ID' 1 is present in the cache so its value i.e 8 is returned. 
2 5 - No element with 'U_ID' 5 is present in cache so -1 is returned.
2 2 - Element with 'U_ID' 2 is present in cache so its value i.e 6 is returned.

Sample Input 2:

Sample Output 2:

-1
6 1

Hint 1

Hint 2

Hint 3

Try using the brute force approach.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

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

Time Complexity

O(N*M), where ‘N’ denotes the size of the cache and ‘M’ denotes the number of operations.

For each operation, we are iterating the cache of size ‘N’.

Space Complexity

O(N), where ‘N’ denotes the size of the cache.

We maintain a cache in the form of a list of size ‘N’.

(75% EXP penalty)

(100% EXP penalty)

LFU Cache

Aryan Solanki

Interview problems

Python MinHeap Solution O(logN) Solution (Not Most Optimal)

from os import *
from sys import *
from collections import *
from math import *
import heapq


# Using Heap
class LFUCache:

    def __init__(self, capacity: int):
        self.dic={}
        self.capacity=capacity
        self.heap=[]

    def get(self, key: int) -> int:
        if key in self.dic:
            heapIndex=self.heap.index([self.dic[key][1],key])
            count,key=self.heap[heapIndex]
            count+=1
            self.heap[heapIndex]=[count,key]
            heapq.heapify(self.heap)
            self.dic[key][1]=count
            return self.dic[key][0]
        else:
            return -1

    def put(self, key: int, val: int) -> None:
        if len(self.dic)==self.capacity:
            count,delKey=heapq.heapreplace(self.heap,[0,key])
            del self.dic[delKey]
        else:
            heapq.heappush(self.heap,[0,key])
        self.dic[key]=[val,0]

python

64 views

0 replies

0 upvotes

Aryan Solanki

Interview problems

Python HashMap and LinkedList Most Optimal O(1) Solution

from os import *
from sys import *
from collections import *
from math import *
import heapq


class Node:
    def __init__(self,key,val):
        self.key=key
        self.val=val
        self.next=None
        self.prev=None
        self.freq=1

class DoubleyLinkedList:
    def __init__(self):
        self.head=Node(0,0)
        self.tail=Node(0,0)
        self.head.next=self.tail
        self.tail.prev=self.head

class LFUCache:
    def __init__(self, capacity: int):
        self.dic={}
        self.freqDic={}
        self.capacity=capacity
        self.minFreq=1

    def get(self, key: int) -> int:
        if key in self.dic:
            node=self.dic[key]
            freq=node.freq+1
            if node.prev.prev==None and node.next.next==None and node.freq==self.minFreq:
                self.minFreq+=1
            node.prev.next=node.next
            node.next.prev=node.prev
            if freq not in self.freqDic:
                self.freqDic[freq]=DoubleyLinkedList()
            temp=self.freqDic[freq].tail.prev
            node.prev=temp
            node.next=self.freqDic[freq].tail
            temp.next=node
            self.freqDic[freq].tail.prev=node
            return node.val
        else:
            return -1
        
    def put(self, key: int, val: int) -> None:
        if len(self.dic)==self.capacity:
            minFreq=self.minFreq
            LFUDoubleyLinkedList=self.freqDic[minFreq]
            del self.dic[LFUDoubleyLinkedList.head.next.key]
            LFUDoubleyLinkedList.head.next=LFUDoubleyLinkedList.head.next.next
            LFUDoubleyLinkedList.head.next.prev=LFUDoubleyLinkedList.head
        node=Node(key,val)
        if 1 not in self.freqDic:
            self.freqDic[1]=DoubleyLinkedList()
        temp=self.freqDic[1].tail.prev
        node.prev=temp
        node.next=self.freqDic[1].tail
        temp.next=node
        self.freqDic[1].tail.prev=node
        self.dic[key]=node

python

46 views

0 replies

0 upvotes

deepak jain

Interview problems

easy c++

#include <bits/stdc++.h> 
class LFUCache
{
public:
    unordered_map<int,int> mp;
    int n;
    LFUCache(int capacity)
    {
        // Write your code here.
        mp.clear();
        n=capacity;
    }

    int get(int key)
    {
        // Write your code here.
        if(mp.find(key)==mp.end())
        return -1;
        return mp[key];

    }

    void put(int key, int value)
    {
        // Write your code here.
        if(mp.find(key)!=mp.end())
        mp[key]=value;
        else if(n>mp.size())
        {
            mp[key]=value;
            
        }
        else
        {
            int mini=INT_MAX;
            int mikey=INT_MAX;
            for(auto x: mp)
            {
                if(x.second<mini)
                {
                    mini=x.second;
                    mikey=x.first;
                }
            }
            mp.erase(mikey);
            mp[key]=value;
        }
    }
};

328 views

0 replies

3 upvotes

Saransh Jaiswal

Interview problems

C++, O(1) time complexity, using node

#include<bits/stdc++.h>
struct Node {
    int key, value, cnt;
    Node *next; 
    Node *prev;
    Node(int _key, int _value) {
        key = _key;
        value = _value; 
        cnt = 1; 
    }
}; 
struct List {
    int size; 
    Node *head; 
    Node *tail; 
    List() {
        head = new Node(0, 0); 
        tail = new Node(0,0); 
        head->next = tail;
        tail->prev = head; 
        size = 0;
    }
    
    void addFront(Node *node) {
        Node* temp = head->next;
        node->next = temp;
        node->prev = head;
        head->next = node;
        temp->prev = node;
        size++; 
    }
    
    void removeNode(Node* delnode) {
        Node* delprev = delnode->prev;
        Node* delnext = delnode->next;
        delprev->next = delnext;
        delnext->prev = delprev;
        size--; 
    }
    
    
    
};

class LFUCache
{
    map<int, Node*> keyNode; 
    map<int, List*> freqListMap; 
    int maxSizeCache;
    int minFreq; 
    int curSize;

public:

    

    LFUCache(int capacity)
    {
        // Write your code here.
        maxSizeCache = capacity; 
        minFreq = 0;
        curSize = 0; 
    }

     void updateFreqListMap(Node *node) {
        keyNode.erase(node->key); 
        freqListMap[node->cnt]->removeNode(node); 
        if(node->cnt == minFreq && freqListMap[node->cnt]->size == 0) {
            minFreq++; 
        }
        
        List* nextHigherFreqList = new List();
        if(freqListMap.find(node->cnt + 1) != freqListMap.end()) {
            nextHigherFreqList = freqListMap[node->cnt + 1];
        } 
        node->cnt += 1; 
        nextHigherFreqList->addFront(node); 
        freqListMap[node->cnt] = nextHigherFreqList; 
        keyNode[node->key] = node;
    }

    int get(int key)
    {
        // Write your code here.
        if(keyNode.find(key) != keyNode.end()) {
            Node* node = keyNode[key]; 
            int val = node->value; 
            updateFreqListMap(node); 
            return val; 
        }
        return -1; 
    }

    void put(int key, int value)
    {
        // Write your code here.
        if (maxSizeCache == 0) {
            return;
        }
        if(keyNode.find(key) != keyNode.end()) {
            Node* node = keyNode[key]; 
            node->value = value; 
            updateFreqListMap(node); 
        }
        else {
            if(curSize == maxSizeCache) {
                List* list = freqListMap[minFreq]; 
                keyNode.erase(list->tail->prev->key); 
                freqListMap[minFreq]->removeNode(list->tail->prev);
                curSize--; 
            }
            curSize++; 
            // new value has to be added who is not there previously 
            minFreq = 1; 
            List* listFreq = new List(); 
            if(freqListMap.find(minFreq) != freqListMap.end()) {
                listFreq = freqListMap[minFreq]; 
            }
            Node* node = new Node(key, value); 
            listFreq->addFront(node);
            keyNode[key] = node; 
            freqListMap[minFreq] = listFreq; 
        }
    }
};

programming

node

112 views

0 replies

0 upvotes

Shahid Akhtar

Interview problems

C++ || Time: [Get: O(1) Put: O(1)] || Space: O(N)

#include<bits/stdc++.h>

using namespace std;

class LFUCache {

int capacity;

int minFreq;

unordered_map<int,pair<int,int>> cache;

unordered_map<int,list<int>> freq_map;

unordered_map<int,list<int>::iterator> pos;

public:

LFUCache(int capacity) {

this->capacity = capacity;

minFreq = 0;

}

int get(int key) {

if(cache.find(key) != cache.end()){

int freq = cache[key].second;

freq_map[freq].erase(pos[key]);

freq++;

freq_map[freq].push_front(key);

pos[key] = freq_map[freq].begin();

if(freq_map[minFreq].empty())

minFreq++;

return cache[key].first;

}else

return -1;

}

void put(int key, int value) {

if(cache.find(key) != cache.end()){

cache[key].first = value;

int freq = cache[key].second;

freq_map[freq].erase(pos[key]);

freq++;

freq_map[freq].push_front(key);

pos[key] = freq_map[freq].begin();

if(freq_map[minFreq].empty())

minFreq++;

return;

}

if(capacity == cache.size()){

int key = freq_map[minFreq].back();

cache.erase(key);

pos.erase(key);

freq_map[minFreq].pop_front();

}

cache[key] = {value, 1};

freq_map[1].push_front(key);

pos[key] = freq_map[1].begin();

minFreq=1;

}

};

255 views

0 replies

0 upvotes

Husain Champawala

Interview problems

C++ Solution

#include <bits/stdc++.h>
struct Node {
  int key, val, freq;
  Node *prev, *next;

  Node(int _key, int _val) { key = _key, val = _val, freq = 1; }
};

struct List {
  Node *head;
  Node *tail;
  int size;

  List() {
    size = 0;
    head = new Node(-1, -1);
    tail = new Node(-1, -1);
    head->next = tail;
    tail->prev = head;
  }

  void addNewNode(Node *newNode) {
    Node *temp = head->next;
    newNode->next = temp;
    newNode->prev = head;
    head->next = newNode;
    temp->prev = newNode;
    size++;
  }

  void deleteNode(Node *delNode) {
    delNode->next->prev = delNode->prev;
    delNode->prev->next = delNode->next;
    size--;
  }
};

class LFUCache {
  unordered_map<int, Node *> mp;
  unordered_map<int, List *> freqList;
  int minFreq, cap, currSize;

public:
  LFUCache(int capacity) {
    minFreq = 0;
    cap = capacity;
    currSize = 0;
  }

  void updateList(Node *node) {
    mp.erase(node->key);
    freqList[node->freq]->deleteNode(node);

    if (freqList[node->freq]->size == 0 or node->freq == minFreq)
      minFreq++;

    List *newList = new List();
    if (freqList.count(node->freq + 1))
      newList = freqList[node->freq + 1];

    node->freq += 1;
    newList->addNewNode(node);
    freqList[node->freq] = newList;
    mp[node->key] = node;
  }

  int get(int key) {
    if (mp.count(key)) {
      Node *node = mp[key];
      int x = node->val;
      updateList(node);
      return x;
    }
    return -1;
  }

  void put(int key, int value) {
    if (cap == 0)
      return;

    else if (mp.count(key)) {
      Node *node = mp[key];
      node->val = value;
      updateList(node);
    }

    else {
      if (currSize == cap) {
        List *list = freqList[minFreq];
        mp.erase(list->tail->prev->key);
        list->deleteNode(list->tail->prev);
        currSize--;
      }

      currSize++;
      minFreq = 1;

      List *list = new List();
      if (freqList.count(minFreq))
        list = freqList[minFreq];

      Node *newNode = new Node(key, value);
      list->addNewNode(newNode);
      freqList[minFreq] = list;
      mp[key] = newNode;
    }
  }
};

LFU Cache

288 views

0 replies

0 upvotes

Codestudio

Interview problems

Discussion thread on Interview Problem | LFU Cache

Hey everyone, creating this thread to discuss the interview problem - LFU Cache.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): LFU Cache

306 views

4 replies

1 upvote

Console