Leetcode: LRU Cache

 This problem is frequently asked at Amazon, Facebook, Bloomberg, and Microsoft (and Twitch) and uses a term in Operating Systems called the Least Recently used Cache. This was taught in the CS 537 class at my university. This is more of a design problem than an actual algorithms problem.

The Problem is "Design a Data Structure that follows the constraints of a Least Recently Used (LRU) cache). The task is to implement the LRUCache class.

The first requirement is to initialize the LRU Cache with positive size capacity with the method enumerated as LRUCache(int capacity).

The second method to implement is to get the key value if a key exists, otherwise return -1 and this is denoted by the method int get(int key). 

The final method is to update the value of the key if the key exists; else add the key-value pair to the cache. Evict the least recently used key if the capacity is exceeded and this is denoted by void put(int key, int value).

The following are samples:

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

Here, the cache size is 2 and initialized as null and always evicts the least  used value, which I believe will be denoted by a variable.

 This is pretty similar to how browsers work, such as remove browsers. We also want to solve this in constant time, which will be kind of tricky. We can design a hashmap for this task. We can try to have a value to be a pointer to the node itself. I can keep track of the most recently used and least recently used through a left and right pointer, and we will be swapping some particular nodes, so this means we need a doubly linked list. We just exchange the left and right pointers at each step along the way. 

Now, I'm going to attempt to implement this solution in Java, and will try my best to explain the author's justifications.

Here is adding a node and removing a node, respectively.

Here is the initialization of the cache, with only 2 nodes, the head and the tail.

The get method basically moves the node to the head, and then returns the value in the arbitrary head.

import java.util.Hashtable;

public class LRUCache {

    class DLinkedNode {

        int key;

        int value;

        DLinkedNode pre;

        DLinkedNode post;

    }

    private void addNode(DLinkedNode node) {

        node.pre = head;

        node.post = head.post;

        head.post.pre = node;

        head.post = node;

    }

    private void removeNode(DLinkedNode node){

        DLinkedNode pre = node.pre;

        DLinkedNode post = node.post;

        pre.post = post;

        post.pre = pre;

    }

    private void moveToHead(DLinkedNode node) {

        this.removeNode(node);

        this.addNode(node);

    }

    private DLinkedNode popTail(){

        DLinkedNode res = tail.pre;

        this.removeNode(res);

        return res;

    }

    private Hashtable<Integer, DLinkedNode> cache = new Hashtable<Integer, DLinkedNode>();

    private int count;

    private int capacity;

    private DLinkedNode head, tail;

    public LRUCache(int capacity) {

        this.count = 0;

        this.capacity = capacity;

        head = new DLinkedNode();

        head.pre = null;

        tail = new DLinkedNode();

        tail.post = null;

        head.post = tail;

        tail.pre = head;

    }

    public int get(int key) {

        DLinkedNode node = cache.get(key);

        if(node == null) return -1;

        this.moveToHead(node);

        return node.value;

    }

    public void put(int key, int value){

        DLinkedNode node = cache.get(key);

        if(node == null) {

            DLinkedNode newNode = new DLinkedNode();

            newNode.key = key;

            newNode.value = value;

            this.cache.put(key, newNode);

            this.addNode(newNode);

            ++count;

            if(count > capacity) {

                DLinkedNode tail = this.popTail();

                this.cache.remove(tail.key);

                --count;

            }

        } else {

            node.value = value;

            this.moveToHead(node);

        }

    }

}

So basically each node added is added to the front of the line and the removal operates as a normal linked list removal. In summary, use a hashmap, double linked list, keep track of the hashmap to get O(1) time, and performed regular linked list removal with a pre and post element. If adding node again, put this node in the head for most recently used attribute.