LRU Cache

Problem

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.

The functions get and put must each run in O(1) average 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

 

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 104
• 0 <= value <= 105
• At most 2 * 105 calls will be made to get and put.

Solution

class LRUCache {
    constructor(capacity) {
        this.maxCapacity = capacity;
        this.curCapacity = 0;
        this.map = new Map();
        this.iterator = this.map.keys();
    }

    get(key) {
        if (this.map.has(key)) {
            const val = this.map.get(key);
            this.map.delete(key);
            this.map.set(key, val);
            return val;
        } else {
            return -1;
        }
    }

    put(key, value) {
        if (this.map.has(key)) {
            this.map.delete(key);
            this.curCapacity--;
        }
        if (this.curCapacity === this.maxCapacity) {
            this.map.delete(this.iterator.next().value);
            this.map.set(key, value);
        } else {
            this.map.set(key, value);
            this.curCapacity++;
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

We will implement a solution using an ordered hashmap map (ordered by insertion). For both put and get, if key exists in map, we simply delete it and reinsert it into map, as this pushes it to the back of iterator. In put, if maxCapacity is reached, we simply delete the key value pair at the front of iterator, as it is the least recently used (and insert a new entry into map as normal).

Another more standard solution is to use a normal hashmap and a doubly linked list. More specifically, the hashmap will contain keys that are associated with nodes of the list, and the node itself is what contains value. The list is sorted in order of usage time (ie. the front of the list is the most recently used, and the end of the list is the least recently used). Thus,

• get can be implemented by returning the value of the corresponding node and moving it to the front of the list.
• put can be implemented by creating a node with value (putting the node in map associated with key) and making it the head of the list.
  • If key already exists in the map, update value of the node and move the node to the front of the list (instead of creating a new node).
  • If the capacity is full, remove the tail of the list and proceed with creating the new node.

All this can be done in O(1) time.