LeetCode 146. LRU Cache

[wupangyen]

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.

[wupangyen]

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

[wupangyen]

When the question mention about get and put need to be O(1) we need to think about hashmap, also when we are dealing with LRU cache, we need to the functionality of add and remove to keep track of which element is most recently use and least recently use. for O(1) and we can think about using doubly linked list.

first we need to define the doubly linked list class we have key, val which stores the key and val when using put function, and we have two node prev and next.

in the constructor we define our hashmap the key is in integer, the value is a doubly linked list

we set up our linked list for LRU cache

we create two extra helper function one is add for adding the node in the front of the doubly linked list.

one is remove we remove a node.

for the method first if we call put we remove the node we are accessing first and add it to the front of the cache doubly linked list. that node become the most recently access

when we call the put functionality if we reached the capacity we need to first remove the least access node

at the end we create a new node assign the new key and val put it in map add it in the linked list

for the get func if the node don't exist we return -1; we access the val by get the node from the map by key

[wupangyen]

class LRUCache { final DListNode head = new DListNode(); final DListNode tail = new DListNode(); Map<Integer,DListNode> d_node_map; int cache_capacity;

public LRUCache(int capacity) {
    d_node_map = new HashMap<Integer,DListNode>();
    this.cache_capacity = capacity;
    head.next = tail;
    tail.prev = head;

}

public int get(int key) {
    // if the value try to get didn't exist
    int result = -1;
    DListNode node = d_node_map.get(key);
    if(node!= null){
        result = node.val;
        remove(node);
        add(node);
    }

    return result;
}

public void put(int key, int value) {
    DListNode node = d_node_map.get(key);
    if(node != null){
        //when we are over riding a node we
        // need to put the node to the front of the d_linked list at the most
        //recent use one
        remove(node);
        node.val = value;
        add(node);
    }
    else{
        // when the size is >= the capacity we need to remove the least used node
        if(d_node_map.size() == cache_capacity){
            // remove from the map
            d_node_map.remove(tail.prev.key);
            // remove from the d_linked_list
            remove(tail.prev);
        }
        DListNode new_node = new DListNode();
        // set the key for the node just add
        new_node.key = key;
        new_node.val = value;

        d_node_map.put(key,new_node);
        // most recent access
        add(new_node);

    }

}

// add at the head of D_linked_list
public void add(DListNode d_node){
    DListNode head_next = head.next;
    d_node.next = head_next;
    head_next.prev = d_node;
    head.next = d_node;
    d_node.prev = head;

}
public void remove(DListNode d_node){

    DListNode next_node = d_node.next;
    DListNode prev_node = d_node.prev;

    next_node.prev = prev_node;
    prev_node.next = next_node;

}

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

}

}

/**

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

[wupangyen]

O(1) time O(n) space