460. 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
public class LFUCache {
// get: O(logn). put: O(logn)
    private int timeStamp;
    private int capacity;
    HashMap<Integer, Node> hashMap;
    TreeMap<Node, Integer> treeMap;
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.timeStamp = 0;
        hashMap = new HashMap<Integer, Node>();
        treeMap = new TreeMap<Node, Integer>(new Comparator<Node> () {
            public int compare(Node n1, Node n2) {
                if (n1.freq == n2.freq) {
                    return n1.timeStamp - n2.timeStamp;
                }
                return n1.freq - n2.freq;
            }
        });
    }
    
    public int get(int key) {
        if (!hashMap.containsKey(key) || capacity == 0) {
            return -1;
        }
        Node old = hashMap.get(key);
        remove(key, old);
        Node newNode = new Node(old.value, ++old.freq, timeStamp++);
        insert(key, newNode);
        return old.value;
    }
    
    public void put(int key, int value) {
        if (capacity == 0) return;
        if (hashMap.containsKey(key)) {
            Node old = hashMap.get(key);
            remove(key, old);
            Node newNode = new Node(value, old.freq + 1, timeStamp++);
            insert(key, newNode);
        } else {
            if (hashMap.size() == capacity) {
                // Cause we defined remove method, do not use pollFirstEntry()
                remove(treeMap.firstEntry().getValue(), treeMap.firstEntry().getKey());
            }
            Node newNode = new Node(value, 1, timeStamp++);
            insert(key, newNode);
        }
    }
    
    class Node {
        private int value, freq;
        private int timeStamp;
        Node(int value, int freq, int timeStamp) {
            this.value = value;
            this.freq = freq;
            this.timeStamp = timeStamp;
        }
    }
    
    public void remove(int key, Node node) {
        hashMap.remove(key);
        treeMap.remove(node);
    }
    
    public void insert(int key, Node node) {
        hashMap.put(key, node);
        treeMap.put(node, key);
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

// The same as above.
public class LFUCache {

    int capacity;
    long timeStamp;
    HashMap<Integer, Node> hashMap;
    TreeMap<Node, Integer> treeMap;
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.timeStamp = 0;
        hashMap = new HashMap<>();
        treeMap = new TreeMap<>(new Comparator<Node>() {
            public int compare(Node n1, Node n2) {
                if (n1.freq == n2.freq) {
                    if (n1.timeStamp - n2.timeStamp < 0) return -1;
                    else if (n1.timeStamp - n2.timeStamp > 0) return 1;
                    else return 0;
                } else {
                    if (n1.freq - n2.freq < 0) return -1;
                    else if (n1.freq - n2.freq > 0) return 1;
                    else return 0;
                }
            }
        });
    }
    
    public int get(int key) {
        if (!hashMap.containsKey(key)) {
            return -1;
        }
        Node old = hashMap.get(key);
        treeMap.remove(old);
        Node newNode = new Node(old.value, old.freq + 1, timeStamp++);
        hashMap.put(key, newNode);
        treeMap.put(newNode, key);
        return old.value;
    }
    
    public void put(int key, int value) {
        if (hashMap.containsKey(key)) {
            Node old = hashMap.get(key);
            treeMap.remove(old);
            Node newNode = new Node(value, old.freq + 1, timeStamp++);
            hashMap.put(key, newNode);
            treeMap.put(newNode, key);
        } else {
            if (capacity == 0) return;
            if (hashMap.size() == capacity) {
                hashMap.remove(treeMap.pollFirstEntry().getValue());
            }
            Node newNode = new Node(value, 1, timeStamp++);
            hashMap.put(key, newNode);
            treeMap.put(newNode, key);
        }
    }
    
    public class Node {
        int value, freq;
        long timeStamp;
        Node(int value, int freq, long timeStamp) {
            this.value = value;
            this.freq = freq;
            this.timeStamp = timeStamp;
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s