146. LRU Cache

Description

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.

Constraints

• 1 <= capacity <= 3000

• 0 <= key <= 3000

• 0 <= value <= 104

• At most 3 * 104 calls will be made to get and put.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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:

Solutions

Solution 1

/**
 * Time complexity : O(1) both for put and get since all operations with 
 *    ordered dictionary. get/in/set/move_to_end/popitem 
 *    (get/containsKey/put/remove) are done in a constant time.
 * Space complexity : O(capacity) since the space is used only for an 
 *    ordered dictionary with at most capacity + 1 elements.
 */

class LRUCache extends LinkedHashMap<Integer, Integer> {
    
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}

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

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class LRUCache {
    
    class Node {
        int key;
        int value;
        Node prev;
        Node next;
        
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private int capacity;
    private Node head;
    private Node tail;
    private Map<Integer, Node> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap();
    }
    
    public int get(int key) {
        Node node = cache.get(key);
        if(node == null) return -1;
        
        removeNode(node);
        offerNode(node);
        
        return node.value;
    }
    
    public void put(int key, int value) {
        if(cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;

            removeNode(node);
            offerNode(node);
        } else {
            if(cache.size() >= capacity) {
                cache.remove(head.key);
                removeNode(head);
            }
            
            Node node = new Node(key, value);
            offerNode(node);
            cache.put(key, node);
        }
    }
    
    private void offerNode(Node node) {
        if(tail != null) {
            tail.next = node;
        }
        
        node.next = null;
        node.prev = tail;
        tail = node;
        
        if(head == null) {
            head = tail;
        }
    }
    
    private void removeNode(Node node) {
        if(node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }
        
        if(node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;
        }
    }
}

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

Follow up

• Could you do get and put in O(1) time complexity?