# LFU cache and Java implementation

I found this one on [VOZ forum](https://voz.vn/) when a member shared about Shopee coding interview. And this is one of the most interesting problems on Leetcode in my opinion. I need to combine both fancy data structures **HashMap** and **LinkedList** in my solution. Today, to enjoy my weekend, I will explain how I implement the **LFU cache**.



![image.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1664611595217/hOX3rtzjU.png align="left")

# I. Preparation

A cache always has 2 main functions: **get** and **put**. And the requirements here are **get** and **put** method must run in O(1) average time complexity. 

=> we will store data in a **Hashmap**.


![image.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1664611899901/DBKC9w0eM.png align="left")

we invalidate and remove the **least frequently used** key. When there are 2 or more keys with the same frequency, we will remove the **least recently used** key. 
 
=> we will store the frequency of keys in a Hashmap <**Frequency**, **LinkedList of Key**> and will maintain the **least recently used** by the LinkedList of keys in the value.

=> we also need to maintain what is the **min frequency** of **cache**, so when you update the freqMap, you also need to update the min frequency.

And this is my note before I implement:

- class **LFUCache**: 
   + capacity
   + min freq
   + freqMap: map of (freq, double linked list of nodes)
   + cache: map of (key, node)

- **get**:
   + if not exist: return -1
   + if exist:
        * check if the node has freq = min_freq and list size == 0 => min_freq++ (because after that we will increase cur freq by 1)
        * increase node frequency by 1
        * remove the node from the current LinkedList in freqMap and insert it to the head of the list at **freq + 1** key
        * return value


- **put**:
   + if exist: update the value of the key in the **cache**, increase the freq of the node by 1, and update freqMap with the new freq.
   + else:
       + full capacity: get linked list from **freqMap** by min freq of **cache**, remove the last node in **freqMap** and **cache**.
       + create a new node with freq = 1, reset min freq to 1
       + insert to **freqMap**: get the cur list or create a new list if not exist, add the new one, and put the list again.
       + insert into **cache**.

# II. Implementation

Phewwww, here is my implementation:


```
import java.util.HashMap;
import java.util.Map;

class LFUCache {

  private int capacity;
  private int minFreq;
  private Map<Integer, DoubleLinkedList> freqMap = new HashMap<>();
  private Map<Integer, Node> cache = new HashMap<>();

  public LFUCache(int capacity) {
    this.capacity = capacity;
  }

  public int get(int key) {
    if (!cache.containsKey(key)) return -1;
    Node node = cache.get(key);
    updateFreqList(node);
    return node.val;
  }

  public void put(int key, int value) {
    if (capacity == 0) return;
    // update value and frequency when exist
    if (cache.containsKey(key)) {
      Node node = cache.get(key);
      node.val = value;
      updateFreqList(node);
    } else {
      // remove when cache is full
      if (cache.size() == capacity) {
        DoubleLinkedList minFreqList = freqMap.get(minFreq);
        Node minNode = minFreqList.removeLast();
        cache.remove(minNode.key);
      }
      
      Node newNode = new Node(key, value);
      minFreq = 1;
      DoubleLinkedList curList = freqMap.getOrDefault(1, new DoubleLinkedList());
      curList.add(newNode);
      freqMap.put(1, curList);
      cache.put(key, newNode);
    }
  }

  private void updateFreqList(Node node) {
    // remove node from cur list
    DoubleLinkedList curList = freqMap.get(node.frequency);
    curList.remove(node);
    
    if (node.frequency == minFreq && curList.size == 0) minFreq++;

    node.frequency++;
    // insert into new list with new freq
    DoubleLinkedList newList = freqMap.getOrDefault(node.frequency, new DoubleLinkedList());
    newList.add(node);
    freqMap.put(node.frequency, newList);
  }

  class Node {
    int key;
    int val;
    Node next;
    Node prev;
    int frequency;

    public Node(int k, int v) {
      key = k;
      val = v;
      frequency = 1;
    }
  }

  class DoubleLinkedList {
    Node head;
    Node tail;
    int size;

    public DoubleLinkedList() {
      this.size = 0;
      head = new Node(0, 0);
      tail = new Node(0, 0);
      head.next = tail;
      tail.prev = head;
    }

    public void add(Node node) {
      node.next = head.next;
      head.next.prev = node;
      node.prev = head;
      head.next = node;
      size++;
    }

    public void remove(Node node) {
      node.prev.next = node.next;
      node.next.prev = node.prev;
      size--;
    }

    public Node removeLast() {
      if (size > 0) {
        Node tailNode = tail.prev;
        remove(tailNode);
        return tailNode;
      }
      return null;
    }
  }
}

``` 

# III. Result

Phewwwww, it's done. I implemented my own doubly linked list, and compare it with when I use **LinkedList of Java Core**.  Surprisingly, my own linked list had better runtime (149ms) while Java core's **LinkedList** triple (509ms). That may be because the **core LinkedList** needs to do many other actions (when we add and remove) rather than focusing on only this problem =)))



![image.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1664614665890/7QdSuwqmG.png align="left")

Okay, that's all for today's post.

# IV. Enjoy your weekend

By the way, let's see =))). Autumn has already come. Go out and enjoy now =)))

![thu_3-09_56_22_226 (2).jpg](https://cdn.hashnode.com/res/hashnode/image/upload/v1664616864646/5p7bilyqf.jpg align="left")

Enjoy your weekend!