Question

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?

Answer 1

An LRU cache can be implemented using a hash table for O(1) key access and a deque for maintaining use-order, allowing for O(1) complexity in get and put operations.

Step-by-step explanation:

To design a Least Recently Used (LRU) cache data structure that supports get and put operations in O(1) time complexity, one can implement it using a combination of a hash table and a double-ended queue (deque).

The hash table provides O(1) access to cache items by key, and the deque maintains the items in the order of use, with the least recently used item at the front. To implement the get operation, if the key is found in the hash table, we update its position in the deque to reflect that it was recently used. If the key is not found, we return -1. For the put operation, if the key is not present in the cache, we insert it into both the hash table and the back of the deque. If the cache is full, we remove the front item of the deque and its corresponding entry in the hash table before inserting the new item.

This ensures that the LRU item is always at the front of the deque for quick eviction, and new items are added at the back.