This version is solved via a LinkedHashMap. LinkedHashMap maintains a built-in doubly-linked list and hashtable, i.e. LRU character is built inside a LinkedHashMap.

JDK 1.8 docs says:

1
2
3
4
5
1. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). ... 

2. A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). ...

3. The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.

new in JDK 1.8: protected boolean removeEldestEntry(Map.Entry<K, V> eldest): returns true if this map should remove its eldest entry.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class LRUCache {

    private LinkedHashMap<Integer, Integer> map;
    private int size;
    
    public LRUCache(int capacity) {
        map = new LinkedHashMap<>();
        size = capacity;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            int value = map.remove(key);
            map.put(key, value);
            return value;
        }
        return -1;
    }
    
    // remove, re-insert to keep fresh
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.remove(key);
        } else if (map.size() + 1 > size) {
            map.remove(map.keySet().iterator().next());
        }
        map.put(key, value);
    }
}

/**
 * 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);
 */

Attention that remove() takes in a key parameter.

Lazier: (via JDK 1.8 APIs):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class LRUCache {

    private LinkedHashMap<Integer, Integer> map;
    private final int size;
    
    public LRUCache(int capacity) {
        size = capacity;
        map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > size;
            }
        };
    }
    
    public int get(int key) {
        return map.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        map.put(key, value);
    }
}