<jupyter_start><jupyter_text>LRU CacheDesign a data structure that follows the constraints of a Least Recently Used (LRU) cache.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 <= 104- 0 <= value <= 105- At most 2 * 105 calls will be made to get and put.<jupyter_code>'''
IDEA:
    The idea is manage items in ordered HashMap. It can be immplemented by Dictionary and Doubly
    Linked List. The idea is that PUT will add a key-value pair to the HashMap and the key to the end of the
    Doubly Linked List. GET fetches the value from the HashMap by key and moves the value to the end of linked list
    When eviciting the existing value we just delete the key from the head of the doubled linked list and from HashMap
ANALYSIS:
    All operations are performed in O(1)
'''

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity
        
    def get(self, key: int) -> int:
        if not key in self.cache:
            return -1
        else:
            self.cache.move_to_end(key)
            return self.cache[key]
        
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value

        if self.capacity < len(self.cache):
            self.cache.popitem(last=False)<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup