LRU Cache
Design 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.
Follow up: Could you do both operations in O(1) time complexity?
- How can we do get(key) in O(1)? We think of a hash table
- How can we do put(key, value) in O(1)? Hash table. However, we need to keep track of the least recently used item so that we can delete it when the cache reaches its capacity. How can we keep track of the least recently used item? We think of a doubly linked list that allows us to move element in constant time