:orphan:

LRU Cache
=========

.. highlight:: none

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

Design a data structure that follows the constraints of a `Least
Recently Used (LRU)
cache <https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU>`__.

Implement the ``LRUCache`` class:

- ``LRUCache(int capacity)`` Initialize the LRU cache with **positive**
  size ``capacity``.
- ``int get(int key)`` Return the value of the ``key`` if the key
  exists, otherwise return ``-1``.
- ``void put(int key, int value)`` Update the value of the ``key`` if
  the ``key`` exists. Otherwise, add the ``key-value`` pair to the
  cache. If the number of keys exceeds the ``capacity`` from this
  operation, **evict** the least recently used key.

The functions ``get`` and ``put`` must each run in ``O(1)`` average time
complexity.

 

**Example 1:**

::


   Input
   ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
   [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
   Output
   [null, null, null, 1, null, -1, null, -1, 3, 4]

   Explanation
   LRUCache lRUCache = new LRUCache(2);
   lRUCache.put(1, 1); // cache is {1=1}
   lRUCache.put(2, 2); // cache is {1=1, 2=2}
   lRUCache.get(1);    // return 1
   lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
   lRUCache.get(2);    // returns -1 (not found)
   lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
   lRUCache.get(1);    // return -1 (not found)
   lRUCache.get(3);    // return 3
   lRUCache.get(4);    // return 4

 

**Constraints:**

- ``1 <= capacity <= 3000``
- ``0 <= key <= 10``\ :sup:```4```
- ``0 <= value <= 10``\ :sup:```5```
- At most ``2 * 10``\ :sup:```5``` calls will be made to ``get`` and
  ``put``.

.. highlight:: python

Pattern
-------
Hash Table, Linked List, Design, Doubly-Linked List

Solution
--------
We want all ``get(key)`` and ``put(key, value)`` operations to be :math:`O(1)`. This
nessecitaties the use of a hashmap. The hashmap key-value pairs must be orderd
by usage in a list. Because list insertion and removal need to be done with
every get and put, we use a linked list. Once we exceed our fixed capacity, we
discard the items from the linked list and hashmap. To simplify the linked list
implementation, we use a dummy head and tail node whose keys are negative
values.

Code
----

.. literalinclude:: ../problems/medium/lru-cache/lru_cache__approach_1.py
    :language: python
    :lines: 20-

Test
----
>>> from lru_cache__approach_1 import LRUCache
>>> cache = LRUCache(2)
>>> cache.put(1, 1)
>>> cache.put(2, 2)
>>> cache.get(1)
1
>>> cache.put(3, 3)
>>> cache.get(2)
-1
>>> cache.put(4, 4)
>>> cache.get(1)
-1
>>> cache.get(3)
3
>>> cache.get(4)
4

Complexity
----------
| :math:`n` is the number of entries in the cache
| Get Time: :math:`O(1)`
| Put Time: :math:`O(1)`
| Auxiliary Space: :math:`O(n)` — hash map and linked list

.. autoclass:: lru_cache__approach_1.LRUCache
   :members:
   :show-inheritance:
   :undoc-members:

.. autoclass:: lru_cache__approach_1.Node
   :members:
   :show-inheritance:
   :undoc-members:

.. autoclass:: lru_cache__approach_1.LinkedList
   :members:
   :show-inheritance:
   :undoc-members: