import java.util.HashMap;
import java.util.Map;
public class LRUCache {
private static class DoublyLinkedHashMap {
private static final class Node {
private final int key;
private final int value;
private Node next;
private Node previous;
private Node(int key, int value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "Node[" +
"key=" + key + ", " +
"value=" + value + ']';
}
}
private final int capacity;
private final Map<Integer, Node> keyToNodeMap;
private final Node sentinel;
public DoublyLinkedHashMap(int capacity) {
this.capacity = capacity;
keyToNodeMap = new HashMap<>();
sentinel = new Node(-1, -1);
// Invarinats: sentinel.next has the head of the DLL and sentinel.previous has the tail of the DLL
// Invariants: head is the least recently used key and tail is the most recently used key for the DLL
sentinel.next = sentinel;
sentinel.previous = sentinel;
}
public void put(int key, int val) {
Node toPlace = new Node(key, val);
Node toRemove = keyToNodeMap.remove(key);
removeNodeFromBetweenItsSiblings(toRemove); // to make it the tail
keyToNodeMap.put(key, toPlace);
makeNodeTheTail(toPlace); // make it the tail
// if size exceeded, remove lru - i.e. head of linked list
if (keyToNodeMap.size() > capacity) {
removeLRU();
}
}
public int get(int key) {
if (!keyToNodeMap.containsKey(key)) return -1;
Node toGet = keyToNodeMap.get(key);
removeNodeFromBetweenItsSiblings(toGet); // to make it the tail
makeNodeTheTail(toGet); // update the tail as key's node was most recently accessed
return toGet.value;
}
private void removeNodeFromBetweenItsSiblings(Node toRemove) {
if (toRemove == null) return;
toRemove.previous.next = toRemove.next;
toRemove.next.previous = toRemove.previous;
}
private void makeNodeTheTail(Node toPlace) {
Node previousTail = sentinel.previous;
previousTail.next = toPlace;
sentinel.previous = toPlace;
toPlace.previous = previousTail;
toPlace.next = sentinel;
}
private void removeLRU() {
// head is the least recently used by invariant, so remove it.
Node previousHead = sentinel.next;
sentinel.next = previousHead.next;
previousHead.next.previous = sentinel;
keyToNodeMap.remove(previousHead.key);
}
}
private final DoublyLinkedHashMap linkedHashMap;
public LRUCache(int capacity) {
linkedHashMap = new DoublyLinkedHashMap(capacity);
}
public int get(int key) {
return linkedHashMap.get(key);
}
public void put(int key, int value) {
linkedHashMap.put(key, value);
}
public static void main(String[] args) {
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}
System.out.println(lRUCache.get(2)); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
System.out.printf("%d, %d, %d\n", lRUCache.get(1), lRUCache.get(3), lRUCache.get(4)); // -1, 3,4
}
}
I would appreciate a review of my solution to the LRU Cache problem. All the operations are O(1) as asked in the question (but for some reason it's faster than only 68%). I used the sentinel node to avoid null checks.
CLASS LINKAGE. \$\endgroup\$