Design LCU cache.
Question Explain
This question requires you to design a Least Recently Used (LRU) cache system. In computing, a cache is a hardware or software component that stores data so future requests for that data can be served faster. The LRU algorithm ensures that the most recently used items are kept, while the least recently used items are discarded. It requires an understanding of data structures, particularly linked list and hash table, since these are usually the main components of an LRU cache.
Guidelines to answer this question include:
- Explain how you use data structures in implementing the LRU cache.
- Discuss the 'get' and 'put' operations of the cache.
- Share insight into the time complexity of these operations.
Answer Example 1
An effective way to implement an LRU cache is by using a combination of a doubly linked list and a hash map. The doubly linked list can be used to represent the cache size and keep track of the 'Least Recently Used' element and the 'most recently used' element. The hash map, on the other hand, can be used to check if an item exists in the cache and also to quickly access the node in the linked list.
The 'get' operation would entail checking if an item exists in the cache via the hash map and returning its value. If it is present, we would need to update the linked list to mark the item as 'most recently used'. If the item does not exist, we could simply return -1 or null.
The 'put' operation would involve adding an item to the cache. If the cache is full, i.e., it has reached its capacity, we would need to remove the least recently used item before inserting the new one. The least recently used item is simply the tail of the linked list.
The insertion and removal operations at the head and tail of a doubly linked list, as well as operations on a hash map, have a time complexity of O(1).
Answer Example 2
Another practical way to implement an LRU cache is by utilizing built-in data structures in certain programming languages. For instance, in Python, we could use an OrderedDict. This essentially combines a doubly linked list and a hash map, making it perfect for this use case.
The 'get' operation works by accessing the value of a certain key if it exists and then moving this key-value pair to the end of the OrderedDict to mark it as recently used. If the key does not exist, a default return value should be specified.
The 'put' operation adds a new item to the cache. If the cache is at capacity before the addition, the first or Least Recently Used item in the OrderedDict will be removed. Using the 'move_to_end' method and popitem() functionality helps ensure constant time operations.
The time complexity for get and put operations is O(1) due to the underlying implementation of OrderedDict.