Lintcode 24. LFU Cache

Description:

LFU (Least Frequently Used) is a famous cache eviction algorithm.
For a cache with capacity k, if the cache is full and need to evict a key in it, the key with the lease frequently used will be kicked out.
Implement set(key,value) and get(key) method for LFU cache.
Example:
Given capacity=3

set(2,2)
set(1,1)
get(2)
>> 2
get(1)
>> 1
get(2)
>> 2
set(3,3)
set(4,4)
get(3)
>> -1
get(2)
>> 2
get(1)
>> 1
get(4)
>> 4

Thinking:

LFU(Least Frequently Used) is another type of cache algorithm used to manage memory within in computers, which cache will delete least frequently used data when it reach the capacity.
Like LRU, we still use HashMap to store key value. And we need to use a double Linkedlist to link all the nodes which have same frequence together. Once the node frequence changed, we only need to delete this node from this Linkedlist and put it to another frequency Linkedlist.
For example:

Frequence
head(0)
|
1—> node1->node2->node3
|
3->node4->node5->node6
|
8->node7->node8
|
tail(Integer.MAX_VALUE)

if we call get(8), then we will get:

Frequence
head(0)
|
1—> node1->node2->node3
|
3->node4->node5->node6
|
8->node7
|
9->node8
|
tail(Integer.MAX_VALUE)

In order to achieve the O(1) get and set. We use a LinkedHashSet which also can put the element in the order of entering order. But can remove element in O(1)

Complexity:

The operation of set and get is O(1). And the space complexity is O(n), since we use a HashMap, double LinkedList and LinkedHashSet.

Steps:

Creating two class, one is Frequence and another is Node.
For get(key), first we check whether the map contians this key. If not, return -1; If yes, first check the whether we already have Frequence.freq+1. If yes, delete the node from current LinkedHashSet and put it to the Frequence.freq+1's LinkedHashSet. Or create the Frequence.freq+1 and delete the node from current LinkedHashSet and put it to the new Frequence LinkedHashSet.
Forset(key,value), first we use get(key) to check whether we have this key rather than use map.containsKey(key). Because we can update the node frequence by using get(key). Also if we reach the capacity we should delete the least frequently used data, which must in the LinkedHashSet of head.next.


class Frequence{
    int freq;
    LinkedHashSet<Integer> set;
    Frequence prev;
    Frequence next;
    public Frequence(int freq){
        this.freq = freq;
        set = new LinkedHashSet<>();
    }
}
class Node{
    int key;
    int value;
    Frequence myFreq;
    public Node(int key, int value, Frequence myFreq){
        this.key = key;
        this.value = value;
        this.myFreq = myFreq;
    }
}
public class LFUCache {
    int capacity;
    Map<Integer, Node> map;
    Frequence head;
    Frequence tail;
    // @param capacity, an integer
    public LFUCache(int capacity) {
        // Write your code here
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Frequence(0);
        tail = new Frequence(Integer.MAX_VALUE);
        head.next = tail;
        tail.prev = head;
    }

    // @param key, an integer
    // @param value, an integer
    // @return nothing
    public void set(int key, int value) {
        // Write your code here
        if(get(key)!=-1){
            map.get(key).value = value;
            return;
        }
        if(map.size() == capacity){
            popLFUNode();
        }
        Frequence newFreq = head.next;
        if (newFreq.freq != 1){
            newFreq = new Frequence(1);
            addFreqNode(head, newFreq);
        }
        Node current = new Node(key,value,newFreq);
        map.put(key,current);
        newFreq.set.add(current.key);
    }

    public int get(int key) {
        // Write your code here
        if(map.containsKey(key)){
            Node current = map.get(key);
            int result = current.value;
            Frequence currentFreq = current.myFreq;
            if(currentFreq.next.freq == currentFreq.freq +1){
                current.myFreq = currentFreq.next;
                currentFreq.next.set.add(current.key);
            }
            else{
                Frequence newFreq = new Frequence(currentFreq.freq+1);
                addFreqNode(currentFreq, newFreq);
                current.myFreq = newFreq;
                newFreq.set.add(current.key);

            }
            currentFreq.set.remove(new Integer(current.key));
            if(currentFreq.set.isEmpty()){
                deleteFreqNode(currentFreq);
            }
            return result;
        }
        else{
            return -1;
        }
    }
    private void addFreqNode(Frequence currentFreq, Frequence newFreq){
        newFreq.next = currentFreq.next;
        currentFreq.next.prev = newFreq;
        newFreq.prev = currentFreq;
        currentFreq.next = newFreq;
    }
    private void deleteFreqNode(Frequence currentFreq){
        currentFreq.next.prev = currentFreq.prev;
        currentFreq.prev.next = currentFreq.next;
    }
    private void popLFUNode(){
        Frequence leastFreq = head.next;
        Iterator<Integer> iterator = leastFreq.set.iterator();
        int leastFreqNodeKey = iterator.next();
        leastFreq.set.remove(new Integer(leastFreqNodeKey));
        map.remove(leastFreqNodeKey);
        if(leastFreq.set.isEmpty()){
            deleteFreqNode(leastFreq);
        }

    }
}

Conclusion:

We should note that to delete Frequence node when the LinkedHashSet is empty.

Lintcode 24. LFU Cache