leetcode_146

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

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(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.

The cache is initialized with a positive capacity.

Follow up:

Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Solutions

1. double linked list with hashmap

2. borrowed from others.

3. Use hash map to get/set item in O(1) time.

4. Use double linked list to retain the latest used item in the front and the least used item in the back to evict the leaset used item in O(1) time.

   • remove an item in double linked list with it's reference is O(1) complexity. (Use map to keep the reference).

   • Thus we need another map to save iterators of each item in double linked list.

class LRUCache {
private:
    int size;
    list<int> lru;
    unordered_map<int, list<int>::iterator> mp;
    unordered_map<int, int> kv;

public:
    LRUCache(int capacity) : size(capacity) {}

    int get(int key) {
        if (!kv.count(key))
            return -1;
        else {
            update(key);
            return kv[key];
        }
    }

    void put(int key, int value) {
        if (!kv.count(key) && kv.size() == size) evict();
        update(key);
        kv[key] = value;
    }

    void update(int key) {
        if (kv.count(key)) lru.erase(mp[key]);
        lru.push_front(key);
        mp[key] = lru.begin();
    }

    void evict() {
        kv.erase(lru.back());
        mp.erase(lru.back());
        lru.pop_back();
    }
};

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

Or save key-value pair in double linked list and store each node's iterator in a hashmap.

class LRUCache {
public:
    using kv = pair<int, int>;
    int cap = 0;
    list<kv> lru;
    unordered_map<int, list<kv>::iterator> m;
    LRUCache(int capacity) : cap(capacity) {

    }

    int get(int key) {
        if (!m.count(key))
            return -1;
        else {
            update(key, m[key]->second);
            return m[key]->second;
        }
    }

    void put(int key, int value) {
        if (lru.size() >= cap && !m.count(key))
            evict();
        update(key, value);
    }

    void evict() {
        if (lru.size()) {
            m.erase(lru.back().first);
            lru.pop_back();
        }
    }

    void update(int key, int value) {
        if (m.count(key))
            lru.erase(m[key]);
        lru.emplace_front(key, value);
        m[key] = lru.begin();
    }
};

Or use self-made double linked list.

template <typename K, typename V>
struct List {
    using node = List<K, V>;
    K key;
    V val;
    node * prev;
    node * next;
    List(K k = K(0), V v = V(0), node * prev = NULL, node * next = NULL)
    : key(k), val(v), prev(prev), next(next) {}
};

typedef List<int, int> Node;

class LRUCache {
private:
    int size;
    Node * front;
    Node * back;
    unordered_map<int, Node *> mp;

public:
    LRUCache(int capacity) : size(capacity) {
        front = new Node(); back = new Node(); 
        front->next = back; back->prev = front;
    }

    int get(int key) {
        if (!mp.count(key))
            return -1;
        else {
            update(key, mp[key]->val);
            return mp[key]->val;
        }
    }

    void put(int key, int value) {
        if (mp.size() == size && !mp.count(key)) {
            // remove the last node
            Node * node = back->prev;
            node->prev->next = node->next;
            node->next->prev = node->prev;
            mp.erase(node->key);
            delete(node);
        }
        update(key, value);
    }

    void update(int key, int value) {
        Node * head;
        if (mp.count(key)) {
            // remove from the list
            head = mp[key];
            head->prev->next = head->next;
            head->next->prev = head->prev;
            head->val = value;
            head->next = front->next;
            head->prev = front;
        } else
            head = new Node(key, value, front, front->next);
        // insert after the front node.
        front->next->prev = head;
        front->next = head;
        mp[key] = head;
    }

    ~LRUCache() { for (auto & p : mp) delete p.second; }

};

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

Or use builtin object that combined these two data structures in python.

from collections import OrderedDict

class LRUCache(OrderedDict):

    def __init__(self, capacity: int):
        self.size = capacity

    def get(self, key: int) -> int:
        if key not in self:
            return -1
        else:
            # move this item to the end
            self.move_to_end(key)
            return self[key]

    def put(self, key: int, value: int) -> None:
        if len(self) == self.size and key not in self:
            # delete the first element
            self.popitem(last=False)
        if key in self:
            # move to end
            self.move_to_end(key)
        # in orderedDict, new key is automatically append to the end
        self[key] = value


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