460. LFU Cache

qqiangwu

Follow

Feb 23, 2017 · 2 min read

It seems that we have a similar problem solved. The LRU Cache. Can we reuse the solution?

We can simply maintain a history whose entries are pairs of (element, frequency). The history is ordered by frequency. In this case, PUT is trivial. But what about GET? How to increment an element’s frequency and preserve the order of the history in constant time? If the frequency sequence is like this: 1,2,2,2,2,2,2,2, then we need linear operation to adjust the position of a newly queried element. Yeah, maybe we can use two layers of lists. The top layer list is an ordered list of frequency. Each element of this list is a list of all entries with the same frequency. We call the first layer of lists as List Freq. We call each list of the second layer of lists as List Entry.

Improves

When I am coding the problem, I find that we indeed do not need to ensure that List Freq is ordered, we can simple use a map plus the minimum frequency.

public class LFUCache {
    private static final int NOT_FOUND = -1;
    private static final int INITIAL_FREQ = 1;
    
    private int capacity;
    private int minFreq = 1;
    private Map<Integer, Node> cache = new HashMap();
    private Map<Integer, LinkList> frequency = new HashMap<>();    public LFUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        final Node e = cache.get(key);
        
        if (e != null) {
            incrFrequency(e);
            
            return e.value;
        }
        
        return NOT_FOUND;
    }
    
    private void incrFrequency(final Node e) {
        LinkList list = frequency.get(e.frequency);
        list.remove(e);
        
        if (list.isEmpty()) {
            frequency.remove(list);
            
            if (e.frequency == minFreq) {
                minFreq++;
            }
        }
        
        e.frequency++;
        
        getFreqListOrCreate(e.frequency)
            .add(e);
    }
    
    private LinkList getFreqListOrCreate(final int freq) {
        if (!frequency.containsKey(freq)) {
            frequency.put(freq, new LinkList());
        }
        
        return frequency.get(freq);
    }
    
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        
        final Node e = cache.get(key);
        
        if (e != null) {
            e.value = value;
            incrFrequency(e);
        } else {
            ensureSpace();
            insertNew(key, value);
        }
    }
    
    private void insertNew(final int key, final int value) {
        final Node e = new Node(key, value);
        
        getFreqListOrCreate(INITIAL_FREQ)
            .add(e);
        
        minFreq = INITIAL_FREQ;
        cache.put(key, e);
    }
    
    private void ensureSpace() {
        if (cache.size() == capacity) {
            final LinkList list = frequency.get(minFreq);
            final Node e = list.removeFirst();
            
            cache.remove(e.key);
            
            if (list.isEmpty()) {
                frequency.remove(list);
            }
        }
    }
    
    static class Node {
        int key;
        int value;
        Node prev;
        Node next;
        int frequency = 1;
        
        public Node(final int key, final int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    static class LinkList {
        Node head = new Node(-1, -1);
        Node tail = head;
        
        public boolean isEmpty() {
            return head == tail;
        }
        
        public Node removeFirst() {
            assert !isEmpty();
            
            final Node e = head.next;
            
            remove(e);
            
            return e;
        }
        
        public void remove(final Node e) {
            final Node prev = e.prev;
            final Node next = e.next;
            
            if (e == tail) {
                tail = prev;
                tail.next = null;
            } else {
                prev.next = next;
                next.prev = prev;
            }
        }
        
        public void add(final Node e) {
            tail.next = e;
            e.prev = tail;
            
            tail = e;
            tail.next = null;
        }
    }
}