LRU Cache - Sept. 20, 2020 - Use Java LinkedHashMap, the interviewee is preparing for Google onsite

LRUCach.Java

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
Follow up:
Could you do get and put in O(1) time complexity? 

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Constraints:

1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 104
At most 3 * 104 calls will be made to get and put.


Algo: LinkedHashMap

Map<Integer, ListNode> linkedHashMap

private static class ListNode {
  int value = 0;
  ListNode prev = null;
  ListNode next = null;
}

when we get(key) a given value, I'll move the list node to the tail of our linkedlist

when we put(key, value) - if that key is already in the map, we remove it first. We add a new node with this value to the tail of the linkedlist.
After adding the new node into the structure, we look to see if map.size() > capacity. If map.size() is greater than capacioty, we remove the final node in the linked list. 


public static class LRUCache {

  public static final int NOT_FOUND = -1;

  private final int capacity;
  private final Map<Integer, Integer> map;
  public LRUCache(int capacity) {
    this.capacity = capacity;
    map = new LinkedHashMap<>(capacity * 2, 0.75f, true);
  }
  
  public int get(int key) {
    Integer value = map.get(key);
    if (value == null) return NOT_FOUND;
    return value.intValue();
  }
  
  public void put(int key, int value) {
    map.put(key, value);
    if (map.size() <= capacity) return;
    Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
    if (!iterator.hasNext()) return;
    iterator.next();
  }
}