LRU Cache

lru_cache.py

"""
Description:
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.
You should make both operations to run in O(1) time complexity.

Example:
cache = LRUCache(2);

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
"""

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.cache:
            self.cache.move_to_end(key)
            return self.cache[key]
        else:
            return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key not in self.cache and\
            len(self.cache) == self.capacity:
            self.cache.popitem(last=False)
        self.cache[key] = value
        self.cache.move_to_end(key)