LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support get and put operations.
- get(key): Get the value (which 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.
Can you do both operations in O(1) time complexity?
Input
operations: the operations
Output
the return values of get operations
Examples
Example 1:
Input:
1operations = ``` 2LRUCache 2 3put 1 1 4put 2 2 5get 1 6put 3 3 7get 2 8put 4 4 9get 1 10get 3 11get 4
1 2**Output**: ```` 31 4-1 5-1 63 74
`
Explanation:
See input.
Try it yourself
Solution
Title
Script
Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.
Contrary to popular belief, Lorem Ipsum is not simply random text.
1 >>> a = [1, 2, 3] 2 >>> a[-1] 3 3