Least recent use cache in python Below is LRU Cache class implementation. 

# 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,


I've left out a lot of the details, but most of the methods you can just delegate to the internal ordered dict self.store. 

https://leetcode.com/problems/lru-cache/description/ 

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

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.dic = {}
        self.history_dic = {}
        self.key_dic = {}
        self.current = 0
        self.count = 0
    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if not key in self.dic:return -1
        self.update_history(key)
        return self.dic[key]

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        self.update_history(key)
        if key in self.dic:
            self.dic[key] = value
            return
        if len(self.dic)==self.capacity:
            i = self.current
            while not self.history_dic[i]:
                i += 1
            self.dic.pop(self.history_dic[i])
            self.key_dic.pop(self.history_dic[i])
            self.current = i+1
        self.dic[key] = value

    def update_history(self,key):
        if key in self.key_dic:
            self.history_dic[self.key_dic[key]] = None
        self.history_dic[self.count] = key
        self.key_dic[key] = self.count
        self.count += 1

# Time:  O(1), per operation.
# Space: O(k), k is the capacity of cache.


# 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.
#
# 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
This cache feels like it could be used like a dict but is nowhere near it. Renaming get to __getitem__ and put to __setitem__ would provide a neater feeling here. Even better, since your main storage is a dict, why not subclass it directly. You would benefit of its interface with almost no additional cost. Just replace every self.dic with a simple self.

Then, to support your requirements, you would implement get based on dict.get and put would be plain __setitem__:

class LruCache(dict):
    ...
    def get(self, key):
        return super().get(key, -1)

    put = __setitem__


Second, you seem to envision using this cache only to store integer keys and integer values. This is a strong assumption here and the cache will misbehave if you ever try to .put(None, 42); or even .put(0, 42) for that matter as you do not distinguish it in you test while not self.history_dic[i]:. Instead, you could delete the associated entry and check for existence (while i not in self.history:).

Lastly, your naming can be improved. _dic as part of names is implementation detail and does not really add meaningful value here; count is the number of updates and should probably be named after that fact; as well as current being the currently know "index" of the least recently used element.



Proposed improvements:

from contextlib import suppress
from typing import Any


class LruCache(dict):
    def __init__(self, capacity: int):
        super().__init__()
        self.capacity = capacity
        self._least_recent = 0
        self._number_of_updates = 0
        self._history = {}
        self._keys_indexes = {}

    def get(self, key: Any) -&gt; Any:
        return super().get(key, -1)

    def __getitem__(self, key: Any) -&gt; Any:
        value = super().__getitem__(key)
        self._update_history(key)
        return value

    def __setitem__(self, key: Any, value: Any):
        self._update_history(key)
        while key not in self and len(self) &gt;= self.capacity:
            while self._least_recent not in self._hitory:
                self._least_recent += 1
            del self[self._history[self._least_recent]]
        super().__setitem__(key, value)

    put = __setitem__

    def __delitem__(self, key: Any):
        super().__delitem__(key)
        index = self._keys_indexes.pop(key)
        del self._history[index]
        if index == self._least_recent:
            self._least_recent += 1

    def _update_history(self, key: Any):
        with suppress(KeyError):
            del self._history[self._keys_indexes[key]]
        self._history[self._number_of_updates] = key
        self._keys_indexes[key] = self._number_of_updates
        self._number_of_updates += 1


You’ll note that I changed the check in capacity into a while loop in case someone would change the cache size halfway through the program such as:

cache = LruCache(10)
cache.put(…)
…
cache.put(…)
cache.capacity = 2
cache.put(…)  # cache shrink from 10 to 2 capacity


Dropping elements as soon as the cache.capacity = 2 line is executed is left as an exercise to the reader.