Leecode: LRUCache

The key is how to maintain the "freshness" order of the elements in the cache.

1. Use linked list, the elements are naturally ordered by its inserting(setting) time. However we also have to adjust "freshness" for each Get operation: moving the node to the most-fresh end since it is "viewed".  With only linked list, this operation (find a node, move it to the very front/end) takes O(n) time, not very efficient.  If we can have random access to linked list, it would help decreasing operation time. Can we really do this? Yes. The solution is to use a HashMap<Key, Value>, where the value is the Node object of LinkedList. Now hook this up, given a Key (Integer), we can find its (double) LinkedList Node in constant time,  then moving it to the very front of this list in constant time.  Actually Java provide something similar--LinkedHashMap.
2. The other way to maintain "freshness" of each element is using binary tree. In order to do this, we need to track lastModifiedTime of each element. It is very easy to use an increasing int/long to simulate "time": for each operation, time++;  Since each element have a lastModifedTime, we can build up a binary search tree regarding this lastModifiedTime. Then deleteMin() will remove the oldest elements, and increaseKey() will update the "freshness" of each element; All these will take O(lg(n)). 

Code: implementation of Method 2 using java's TreeMap.

public class LRUCache {
    
    TreeMap tree ;
    HashMap keyValue;
    HashMap keyTime;
    HashMap nodes;
    private final int capacity;
    private int occupy;
    private long i;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        tree = new TreeMap();
        keyValue = new HashMap(this.capacity);
        keyTime = new HashMap(this.capacity);
        occupy = 0;
        i = Long.MIN_VALUE;
        
    }
    
    public int get(int key) {
        if(keyValue.containsKey(key)){
         long lastAccessTime = keyTime.get(key);
         
         tree.remove(lastAccessTime);
         tree.put(++i, key);
         keyTime.put(key, i);
         
         return keyValue.get(key);
        
        }
           
        return -1;
    }
    
    public void set(int key, int value) {
        if(keyValue.containsKey(key))
        {
         long lastAccessTime = keyTime.get(key);
         
         tree.remove(lastAccessTime);
         tree.put(++i, key);
         keyTime.put(key, i);
         
         keyValue.put(key, value);
            
        }else{
            if(occupy < capacity){
             tree.put(++i, key);
             keyTime.put(key, i);
             keyValue.put(key, value);
             occupy++;
            }else{
               //remove oldest
             long oldest = tree.firstKey();
             int oldestKey = tree.remove(oldest);
             keyTime.remove(oldestKey);
             keyValue.remove(oldestKey);
             
             //insert new
             tree.put(++i, key);
             keyTime.put(key, i);
             keyValue.put(key, value);
            }
        }
    }
    
}