LRU cache with O(1) get and put using OrderedDict

# ======================================================================
# Q: Implement an LRU cache with capacity N (get and put in O(1)).
#
# O(1) for both. If asked without OrderedDict: a dict plus a doubly linked list.
# In practice, functools.lru_cache is already available.
# ======================================================================

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)          # most recently used
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)   # evicts the least recently used