In a Meta-style system such as Facebook Feed, recently accessed items are often kept in a fixed-size cache. Design and implement an LRU (Least Recently Used) cache that supports get and put in O(1) average time.
You must implement a cache with a fixed positive capacity:
get(key) returns the value associated with key if it exists, otherwise returns -1.put(key, value) inserts or updates the key-value pair.get or put on an existing key makes that key the most recently used.Implement a class LRUCache with:
LRUCache(capacity: int)get(key: int) -> intput(key: int, value: int) -> NoneUse integer keys and values.
Example 1:
capacity = 2, operations = [put(1,1), put(2,2), get(1), put(3,3), get(2)][null, null, 1, null, -1]1 becomes recently used after get(1), so key 2 is evicted when key 3 is inserted.Example 2:
capacity = 1, operations = [put(1,10), put(2,20), get(1), get(2)][null, null, -1, 20]2 evicts 1.1 <= capacity <= 30000 <= key, value <= 10^92 * 10^5 calls to get and putget and put should run in O(1) average timecapacity = 2, operations = [["put", 1, 1], ["put", 2, 2], ["get", 1], ["put", 3, 3], ["get", 2], ["put", 4, 4], ["get", 1], ["get", 3], ["get", 4]]Output[null, null, 1, null, -1, null, -1, 3, 4]WhyAfter `get(1)`, key `1` becomes most recently used, so key `2` is evicted when `3` is inserted. Later key `1` is evicted when `4` is inserted.capacity = 1, operations = [["put", 1, 10], ["put", 2, 20], ["get", 1], ["get", 2]]Output[null, null, -1, 20]WhyWith capacity 1, inserting key `2` immediately evicts key `1`.1 <= capacity <= 30000 <= key, value <= 10^91 <= operations.length <= 2 * 10^5Each operation is either ["put", key, value] or ["get", key]All get and put operations should run in O(1) average timedef run_lru_cache(capacity, operations):