LRU Cache

 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.

The functions get and put must each run in O(1) average 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

Solution#1 : Built-In

class LRUCache {

int capacity;

LinkedHashMap<Integer, Integer> cache;

public LRUCache(int capacity) {

this.capacity = capacity;

// Initialized LinkedHashMap with initial capacity, load factor and accessOrder

cache = new LinkedHashMap<>(5, 0.75f, true) {

@Override

protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest){

return size() > capacity;

}

};

}

public int get(int key) {

return cache.getOrDefault(key, -1);

}

public void put(int key, int value) {

cache.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);

*/

Solution#2 : Using Doubly LinkedList and Hash Map

class ListNode {

int key;

int val;

ListNode next;

ListNode prev;

public ListNode(int key, int val) {

this.key = key;

this.val = val;

}

}

class LRUCache {

int capacity;

Map<Integer, ListNode> cache;

ListNode head;

ListNode tail;

public LRUCache(int capacity) {

this.capacity = capacity;

cache = new HashMap<>();

head = new ListNode(-1, -1);

tail = new ListNode(-1, -1);

head.next = tail;

tail.prev = head;

}

public int get(int key) {

if (!cache.containsKey(key)) {

return -1;

}

ListNode node = cache.get(key);

remove(node);

addToTail(node);

return node.val;

}

public void put(int key, int value) {

if (cache.containsKey(key)) {

ListNode oldNode = cache.get(key);

remove(oldNode);

}

ListNode node = new ListNode(key, value);

cache.put(key, node);

addToTail(node);

if (cache.size() > capacity) {

ListNode nodeToDelete = head.next;

remove(nodeToDelete);

cache.remove(nodeToDelete.key);

}

}

public void addToTail(ListNode node) {

ListNode previousEnd = tail.prev;

previousEnd.next = node;

node.prev = previousEnd;

node.next = tail;

tail.prev = node;

}

public void remove(ListNode node) {

node.prev.next = node.next;

node.next.prev = node.prev;

}

}

/**

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

*/