1. Find third max in linear time.

Design and implement a data structure for Least Recently Used (LRU) 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 reached its capacity, it should invalidate the least recently used item before inserting a new item.

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

Example:

LRUCache cache = new LRUCache( 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.put(4, 4);    // evicts key 1 
cache.get(1);       // returns -1 (not found) 
cache.get(3);       // returns 3 
cache.get(4);       // returns 4

Understand Problem

LRUCache is like a hash table except we need to keep track of the least recently used key so that when we hit the capacity we can evict this item. Here used means update (put), get, or create (put).

Idea – 1

We use a HashMap and a LinkedList (doubly linked), the linkedlist would be used to keep track of the oldest key. Whenever we get a key we move the node for that key in the linkedlist to the front. Likewise when we update (put for existing key) a key, we move the corresponding node to the front. We insert to the front always. In this way, the tail node always is the oldest and ready to be evicted. All operations are .

class LRUCache {
    
    class Node
    {
        int key;
        int val;
        
        public Node(int key, int val)
        {
            this.key = key;
            this.val = val;
        }
    }
    
    private int capacity;
    private HashMap<Integer, Node> map;
    private LinkedList<Node> list;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        list = new LinkedList<>();
    }
    
    public int get(int key) {
        Node node = map.getOrDefault(key, null);
        
        if(node==null)
        {
            return -1;
        }
        
        list.remove(node);
        list.addFirst(node);
        
        return node.val;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key))
        {
            Node node = map.get(key);
            node.val = value;
            list.remove(node);
            list.addFirst(node);
        }
        else
        {
            if(map.size()==this.capacity)
            {
                Node last = list.removeLast();
                map.remove(last.key);
            }
            
            Node node = new Node(key, value);
            map.put(key, node);
            list.addFirst(node);
        }
    }
}

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

Runtime: 220 ms, faster than 9.21% of Java online submissions for LRU Cache. Memory Usage: 67.6 MB, less than 6.42% of Java online submissions for LRU Cache.

Idea – 2

We extend Java’s built-in LinkedHashMap. We need to override removeEldestEntry method. The default eviction is based on insertion order so we need to switch to access order through passing in true in the constructor.

class LRUCache extends LinkedHashMap<Integer, Integer> {
    
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        Integer val = super.get(key);
        return val==null ? -1 : val;
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }
    
    public boolean removeEldestEntry(Map.Entry<Integer, Integer> entry)
    {
        return super.size() > this.capacity;
    }
}

Runtime: 56 ms, faster than 99.73% of Java online submissions for LRU Cache. Memory Usage: 51.4 MB, less than 95.53% of Java online submissions for LRU Cache.