[LeetCode 146] LRU Cache

Question

link

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Stats

Adjusted Difficulty	4
Time to use	Very difficult

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a difficult question, I can’t write the solution easily even after a month.

Solution

The solution is to use a Doubly-linked-list and a HashMap. Doing this allows O(1) search, remove and insert. A very nice and sophisticated data structure example, and very high frequency in interviews.

2 important things to note while coding:

1. We need 2 helper methods: removeNode() and setNodeAsHead().

   Because we reuse both methods for get() and set() methods.

2. Initialization of LRU

   We need 5 variables: capacity, current size(optional but good to have), hashmap, head, tail.

3. Initialization of DoubleLinkedListNode

   This is easy, but do not forget about both key and value variable. We must use DoubleLinkedListNode.key when we want to delete tail.

Code

Write your own DS: DoubleLinkedList.

public class LRUCache {

    int size;
    int capacity;

    DoubleLinkedList head;
    DoubleLinkedList tail;
    HashMap<Integer, DoubleLinkedList> map;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = null;
        tail = null;
        map = new HashMap<Integer, DoubleLinkedList>();
    }

    public void remove(DoubleLinkedList node) {
        if (node == head && node == tail) {
            head = null;
            tail = null;
        } else if (node == head) {
            head.next.prev = null;
            head = head.next;
        } else if (node == tail) {
            tail.prev.next = null;
            tail = tail.prev;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        node.prev = null;
        node.next = null;
    }

    public void setHead(DoubleLinkedList node) {
        node.next = head;
        node.prev = null;
        if (head != null) {
            head.prev = node;
        }

        head = node;
        if (tail == null) {
            tail = node;
        }
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            // if key is not found
            return -1;
        } else {
            // if key is found
            DoubleLinkedList target = map.get(key);
            remove(target);
            setHead(target);
            return head.val;
        }
    }

    public void set(int key, int value) {
        if (this.get(key) != -1) {
            // key exist before, just replace the old value
            DoubleLinkedList old = map.get(key);
            old.val = value;
        } else {
            // this is a new key-value pair, insert it
            DoubleLinkedList newHead = new DoubleLinkedList(key, value);
            map.put(key, newHead);
            setHead(newHead);
            if (size == capacity) {
                // delete tail
                map.remove(tail.key);
                remove(tail);
            } else {
                size++;
            }
        }
    }

    class DoubleLinkedList {
        int key;
        int val;
        DoubleLinkedList prev;
        DoubleLinkedList next;
        public DoubleLinkedList(int k, int v) {
            this.key = k;
            this.val = v;
        }
    }
}

Updated Nov 17th, 2022

class LRUCache {

    int capacity;
    DoublyLinkedNode head;
    DoublyLinkedNode tail;
    HashMap<Integer, DoublyLinkedNode> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = null;
        tail = null;
        map = new HashMap<Integer, DoublyLinkedNode>();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        } else {
            DoublyLinkedNode target = map.get(key);
            removeNode(target);
            setHead(target);
            return head.val;
        }
    }

    public void put(int key, int value) {
        if (this.get(key) != -1) {
            DoublyLinkedNode curNode = map.get(key);
            curNode.val = value;
        } else {
            // this is a new key-value pair, insert it
            DoublyLinkedNode newHead = new DoublyLinkedNode(key, value);
            map.put(key, newHead);
            setHead(newHead);
            if (map.size() > capacity) {
                map.remove(tail.key);
                removeNode(tail);
            }
        }
    }

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

    private void setHead(DoublyLinkedNode node) {
        node.next = head;
        node.prev = null;
        if (head != null) {
            head.prev = node;
        }

        head = node;
        if (tail == null) {
            tail = node;
        }
    }

    class DoublyLinkedNode {
        int key;
        int val;
        DoublyLinkedNode prev;
        DoublyLinkedNode next;

        public DoublyLinkedNode(int k, int v) {
            this.key = k;
            this.val = v;
        }
    }
}