Least recent use cache in python
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.