<jupyter_start><jupyter_text>ProblemDesign 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, it should invalidate the least recently used item before inserting a new item.The cache is initialized with a positive capacity.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 1cache.put(3, 3);    // evicts key 2cache.get(2);       // returns -1 (not found)cache.put(4, 4);    // evicts key 1cache.get(1);       // returns -1 (not found)cache.get(3);       // returns 3cache.get(4);       // returns 4```  Solution<jupyter_code>class LRUCache:
    from collections import OrderedDict

    def __init__(self, capacity: int):
        self.lru = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.lru:
            return -1
        self.lru.move_to_end(key)
        return self.lru[key]
        
    def put(self, key: int, value: int) -> None:
        if key not in self.lru:
            if len(self.lru) >= self.capacity:
                self.lru.popitem(last=False)
            self.lru[key] = value
        else:
            self.lru[key] = value
            self.lru.move_to_end(key)



# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
obj = LRUCache(2)
obj.put(1,1)
obj.put(2,2)
print(obj.get(1))
obj.put(3,3)
print(obj.get(2))
obj.put(4,4)
print(obj.get(1))
print(obj.get(3))
print(obj.get(4))<jupyter_output>1
-1
-1
3
4
{'fraction_non_alphanumeric': 0.12329485834207765, 'fraction_numerical': 0.023084994753410283, 'mean_word_length': 2.8760162601626016, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '227344', 'license': 'MIT', 'n_tokens_mistral': 659, 'n_tokens_neox': 633, 'n_words': 200, 'path': 'Day_24_LRU_Cache.ipynb', 'repo_name': 'bundickm/LeetCode-30-Day-Challenge', 'size': '1906'}