0146.md

146. LRU Cache

Level:

Topic:

Similar Problem:

• 460. LFU Cache

Question

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

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

Intuition

• Doubly Linked List - to maintain the from most recently used nodes to least recently used nodes
• Hash Map - to store every nodes that's in the list so every node can be easily removed

Structure of Doubly Linked List:

1. keep a head and tail counter node to locate the whole list
2. every new know is being added to the front of the list
   • if the list is empty (head is null), set head and tail to the new added node
   • else, put it in front of head and let head point to the new node
3. the tail node is always the least recently used
4. when removing the node
   • if the it's the head node
     • have head point to the next
     • if both head and tail, means there is only one node in the list, so tail is set to null
   • not head node, it's gotta be any node between head.next and tail
     • set the predecessor node to point to its next, it must have a predecessor node.
     • if it's a tail node, it does not have a next node, so the tail will be set to its predecessor
     • otherwise, just set the succesor to point to current's predecessor
5. when removing the tail node
   • just use the remove function and but set the node to tail
   • since it would also handle the tail node removal

Structure of Least Recently Used:

1. globalize the cache capacity variable
2. GET - returns the value if the node exists in the hashmap
   • if not exists, return -1
   • otherwise, get the node from hashmap and update its position in the doubly linked list
3. PUT - it might be an old key with a new value
   • check if key already presents in the cache
     • if exists, change the value and call GET so its position will be updated
   • otherwise
     • create the new node with the key and value
     • check if the cache is at capacity
       • if true, remove the least recently used node from the list and from the hashmap
     • add the new node to the front of the list and put in the map

Code

Time: O(1)
Space: O(c)

class Node {
    int key;
    int val;
    Node prev;
    Node next;
    Node (int key, int val) {
        this.key = key;
        this.val = val;
    }

    void print() {
        System.out.print(" " + key + ":" + val);
    }
}

class DLL {
    Node head;
    Node tail;

    DLL() { }

    void addNode(Node node) {
        node.prev = null;
        node.next = null;

        if (head == null) {
            head = node;
            tail = node;
        } else {
            head.prev = node;
            node.next = head;
            head = node;
        }
    }

    void removeNode(Node node) {
        if (node == head) {
            if (node == tail)
                tail = null;
            head = head.next;
        } else {
            node.prev.next = node.next;
            if (node == tail)
                tail = tail.prev;
            else
                node.next.prev = node.prev;
        }
    }

    void removeLast() {
        if (tail != null)
            removeNode(tail);
    }

    void print() {
        Node curr = head;
        while (curr != null) {
            curr.print();
            curr = curr.next;
        }
        System.out.println();
    }
}

class LRUCache {

    private int capacity;
    private HashMap<Integer, Node> map = new HashMap<>();
    private DLL list;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.list = new DLL();
    }

    public int get(int key) {
        if (!map.containsKey(key))
            return -1;

        Node node = map.get(key);
        list.removeNode(node);
        list.addNode(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.get(key).val = value;
            this.get(key);
        } else {
            if (map.size() == this.capacity) {
                map.remove(list.tail.key);
                list.removeLast();
            }

            Node node = new Node(key, value);
            map.put(key, node);
            list.addNode(node);
        }
    }
}

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