LRU

Original Problem

Past Solutions

Idea

---

• A Double Linked List allows us to perform LRU cache manipulation in $O(1)$ time, regardless of where the cache is located. However, it takes $O(n)$ time to find the cache given a key. This can be solved with a Hash Map that stores a mapping between the key and the doubly linked list node that holds the cache value for that particular key

Tip

We also make use of Virtual Node to make the linked list operations easy to manage.

Space & Time Analysis

---

The analysis method we are using is Algorithm Complexity Analysis

Space - O(n)

• Ignore input size & language dependent space
• we are using a Hash Map to hold the key-node pairs

Time - O(1)

• Both get() and put() are O(1)

Codes

---

5th Attempt (Java)

class Node {
  int key;
  int val;
 
  Node prev;
  Node next;
 
  public Node() {}
 
  public Node(int key, int val) {
    this.key = key;
    this.val = val;
  }
}
 
class LRUCache {
  Node head;
  Node tail;
  int capacity;
  Map<Integer, Node> map;
 
  public LRUCache(int capacity) {
    this.capacity = capacity;
 
    head = new Node();
    tail = new Node();
    head.next = tail;
    tail.prev = head;
 
    map = new HashMap<>();
  }
 
  public int get(int key) {
    if (!map.containsKey(key))
      return -1;
 
	// Recently used
    Node currNode = map.get(key);
    removeNode(currNode);
    addToHead(currNode);
 
    return currNode.val;
  }
 
  public void put(int key, int value) {
    if (!map.containsKey(key)) {
	  // Evict least used key to create space for new key
      if (capacity <= 0) {
        Node currLast = tail.prev;
        removeNode(currLast);
        map.remove(currLast.key); // remember to remove from the hash map too!
        capacity++;
      }
 
      // New key added
      Node newNode = new Node(key, value);
      map.put(key, newNode);
      addToHead(newNode);
      capacity--;
 
      return;
    }
    
	// Key updated
    Node currNode = map.get(key);
    currNode.val = value;
 
    removeNode(currNode);
    addToHead(currNode);
  }
 
  public void addToHead(Node node) {
    Node currFirst = head.next;
 
    head.next = node;
    currFirst.prev = node;
    node.prev = head;
    node.next = currFirst;
  }
 
  public void removeNode(Node node) {
    Node prevNode = node.prev;
    Node nextNode = node.next;
 
    prevNode.next = nextNode;
    nextNode.prev = prevNode;
 
    node.prev = null;
    node.next = null;
  }
}
 
/**
 * 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);
 */
 

Personal Reflection

---

• Why it takes so long to solve: Rusty with Double Linked List implementation in Java
• What you could have done better: Sketch out the things to note. For example, the place to update the Hash Map and the double linked list
• What you missed: NIL
• Ideas you’ve seen before: hashmap, double linked list
• Ideas you found here that could help you later: NIL
• Ideas that didn’t work and why: NIL