146. LRU Cache

/**

 * 146. 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.

 * 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

*/

This is a very frequently asked interview question.

See solution to the question on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/design/LRUCache.java

We will create methods: removeNode, moveToHead, addNode & popTail to get us simplify code in put and get methods.  In addition, the code will leverage head and tail sentinels to simplify logic.

The intention of the design is to simplify the logic in put and get methods via leveraging the above reusable methods.

Here is the constructor. See below where we create head and tail sentinels.

ListNode head;
ListNode tail;
public LRUCache(int capacity) {
    this.capacity = capacity;
    head = new ListNode();
    tail = new ListNode();
    //initialize head to point to tail and vice versa
    head.next = tail;
    tail.prior = head;
}

Simple method to remove a node and adjust pointers in order to keep the LRU Cache consistent.

void removeNode(ListNode node) {
    nodeMap.remove(node.key);
    node.prior.next = node.next;
    node.next.prior = node.prior;
}

Add Node adds the node as the head. 

void addNode(ListNode node) {
    nodeMap.put(node.key, node);
    node.next = head.next;
    node.prior = head;
    head.next.prior = node;
    head.next = node;
}

Leverages removeNode and addNode to move a node as the head.

void moveToHead(ListNode node) {
    removeNode(node);
    addNode(node);
}

Pops the tail node. This is leveraged when capacity is reached.

ListNode popTail() {
    ListNode actTail = tail.prior;
    tail.prior = tail.prior.prior;
    return actTail;
}

Method to add a new value to the cache.

public void put(int key, int value) {
    if (nodeMap.size() == capacity && !nodeMap.containsKey(key)) {
        ListNode node = popTail();
        removeNode(node);
    }
    ListNode node = nodeMap.get(key);
    if (node != null) {
        // if exists , update value and move to head
        node.val = value;
        moveToHead(node);
    } else {
        //add a new node via addNode method
        node = new ListNode(key, value);
        addNode(node);
    }
}

Method to get a value from the cache and moves the given node if it exists as the next head.

public int get(int key) {
    ListNode node = nodeMap.get(key);
    if (node == null) {
        return -1;
    }
    //move node to head if its in cache
    moveToHead(node);
    return node.val;
}