LFU Cache

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.

Follow up:

Could you do both operations in O(1) time complexity?

Example:

    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

Tips:

需要用两个map存放keys和values，用一个linkedhashset存放出现的顺序。而创造node的时候以（count）为输入，同样count的放在一个node，进行每次操作时increaseCount。每次将新点加入成为第一个点（addToHead)。如果capacity不够，则选择head里的第一个点进行删除，如果head里只有一个key，那么移除head使下一位变成head。

head --- FreqNode1 ---- FreqNode2 ---- ... ---- FreqNodeN | | |
first     first           first
  |         |               |
KeyNodeA KeyNodeE       KeyNodeG
  |         |               |
KeyNodeB KeyNodeF       KeyNodeH
  |         |               |
KeyNodeC   last         KeyNodeI
  |         |               |
KeyNodeD   last           last

Code:

public class LFUCache {

    class Node {
        public int count = 0;
        public LinkedHashSet<Integer> keys;
        public Node prev, next;

        public Node(int count) {
            this.count = count;
            keys = new LinkedHashSet<Integer>();
            prev = null;
            next = null;
        }
    }

    int capacity;
    Node head;
    Map<Integer, Integer> valueMap;
    Map<Integer, Node> nodeMap;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        valueMap = new HashMap<>();
        nodeMap = new HashMap<>();
        head = new Node(0);
    }

    public int get(int key) {
        if (!valueMap.containsKey(key)) return -1;
        increaseCount(key);
        return valueMap.get(key);
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        if (valueMap.containsKey(key)) valueMap.put(key, value);
        else {
            if (valueMap.size() == capacity) removeOld();
            valueMap.put(key, value);
            addToHead(key);
        }
        increaseCount(key);
    }

    private void increaseCount(int key) {
        Node node = nodeMap.get(key);
        node.keys.remove(key);
        if (node.next == null) {            
            node.next = new Node(node.count + 1);
            node.next.prev = node;
            node.next.keys.add(key);
        } else if (node.next.count == node.count + 1) 
            node.next.keys.add(key);
        else {
            Node curt = new Node(node.count + 1);
            curt.keys.add(key);
            curt.prev = node;
            curt.next = node.next;
            curt.next.prev = curt;
            node.next = curt;
        }
        nodeMap.put(key, node.next);
        if (node.keys.size() == 0) removeNode(node);
    }

    private void addToHead(int key) {
        if (head.next == null) {
            head.next = new Node(1);
            head.next.keys.add(key);            
            head.next.prev = head;
        } else if (head.next.count > 1) {
            Node node = new Node(1);
            node.keys.add(key);
            node.next = head.next;
            head.next = node;
            node.prev = head;
            node.next.prev = node;
        } else head.next.keys.add(key);
        nodeMap.put(key, head.next);
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        if (node.next != null) node.next.prev = node.prev;
    }

    private void removeOld() {
        if (head.next == null) return;
        int old = head.next.keys.iterator().next();
        head.next.keys.remove(old);
        if (head.next.keys.size() == 0) removeNode(head.next);
        nodeMap.remove(old);
        valueMap.remove(old);
    }
}