460. LFU Cache

Description

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

• get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
• put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate 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 would be evicted.

Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.

Sample Input and Output

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Sample Input Analysis

Operation	LFU{{key, value, freq}}	Output
put(1, 1)	{{1, 1, 1}}	NA
put(2, 2)	{{2, 2, 1}, {1, 1, 1}}	NA
get(1)	{{1, 1, 2}, {2, 2, 1}}	1
put(3, 3)	{{1, 1, 2}, {3, 3, 1}}	NA
get(2)	{{1, 1, 2}, {3, 3, 1}}	-1
get(3)	{{3, 3, 2}, {1, 1, 2}}	3
put(4, 4)	{{3, 3, 2}, {4, 4, 1}}	NA
get(1)	{{3, 3, 2}, {4, 4, 1}}	-1
get(3)	{{3, 3, 3}, {4, 4, 1}}	3
get(4)	{{3, 3, 3}, {4, 4, 2}}	4

Solutions

Solution 1:

• Data Structure && Algorithm
• Implementation

Data Structure:

• Frequency table: A hashmap to store the mapping of different frequency values with values as DLLs storing (key, value) pairs as nodes
• Cache Dicitionary: Nodes in the DLL are stored as values for each key pushed into the cache

Algorithm:

get(key):

1. If key is not present in cache, return -1
2. Get the node from the cache
3. Update the node frequency
4. Remove the node from the DLL of node’s previous frequency
5. Add the node to the DLL with the node’s updated frequency
6. Update min frequency value

put(key, value):

• If key is present in cache
  1. Similar logic to that of get function
  2. Only difference being that we need to update the value here
• If key not present in cache
  1. If the cache has already reached it’s capacity, delete the tail node from the DLL with least frequency
  2. Create the new node with the (key, value) pair passed as arguments
  3. Add the node to the frequency table with frequency key = 1
  4. Add the node to the cache
  5. Update min frequency to be 1

Double Linked List:

public class LFUCache {

    private Map<Integer, Node> map;
    private Map<Integer, DLinkedList> freq;
    private int capacity;
    private int min_feq;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        freq = new HashMap<>();
        min_feq = 1;
    }

    public int get(int key) {
        if (map.get(key) == null) {
            return -1;
        } else {
            Node node = map.get(key);
            freq.get(node.freq).remove(node);
            if (min_feq == node.freq && freq.get(node.freq).isEmpty()) {
                min_feq++;
            }
            node.freq++;
            freq.computeIfAbsent(node.freq, ignore -> new DLinkedList());
            freq.get(node.freq).push_head(node);
            return node.value;
        }
    }

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

        if (map.get(key) == null) {
            if (map.size() == capacity) {
                Node node = freq.get(min_feq).remove_tail();
                map.remove(node.key);
            }

            Node node = new Node(key, value);
            freq.computeIfAbsent(node.freq, ignore -> new DLinkedList());
            freq.get(node.freq).push_head(node);
            map.put(key, node);
            min_feq = 1;
        } else {
            get(key);
            map.get(key).value = value;
        }

    }

    private class Node {
        int key;
        int freq;
        int value;
        Node prev, next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
            freq = 1;
        }
    }

    private class DLinkedList {
        Node head, tail;
        int size;

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

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

        public Node remove_tail() {
            if (size == 0) {
                return null;
            }


            Node node = tail.prev;

           remove(node);

            return node;
        }

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

            node.next = null;
            node.prev = null;
        }

        public boolean isEmpty() {
            return size == 0;
        }
    }
}

Resource

• 460. LFU Cache