LRU cache is a common interview problem that requires the creative use of two common data structures. The problem you are trying to solve is that you want to store a limited number of items in your cache (e.g. the user's local storage). Let's just say you only want to store a maximum of 10 items in the cache at any given moment.
If a user accesses 10 photos, all is well and the 10 photos are stored in the cache. But when the user wants to access the eleventh photo, you need to remove the photo that was the least recently used from the cache and store the eleventh photo so you don't exceed the size limit of 10 items.
Constraints:
- Inserting a new item in the cache must be done in constant time: O(c)
- Retrieval must be done in constant time: O(c)
- Deleting an old item (the LRU item) in the cache must be done in constant time: O(c)
Basically, everything must be done in constant time. So what's the trick?
You need to use two data structures:
- Linked list allows you to insert a new item in O(c) and delete the least recently used item (the head) in O(c)
- You will also want to keep track of the linked list length
- You will also need a doubly-linked list to ensure O(c) for removing any node from the linked list
- Hash Table allows you to retrieve an item in O(c)
So let's say the user wants to access an item, for example using a photo ID string. You first need to do look up the hash table and see if that key points to a linked list node.
If it doesn't point to a linked list node, you will need to check to see your cache is at capacity. If you are at your limit, you need to remove your least recently used, which will be your head node.
Now, you can fetch data. Then, you create a linked list node using the addToTail method and you reference it in your key-value pair of your hash table. The linked list node will include: 1) the key (e.g. the photo ID string), 2) the value (e.g. the bits of the photo) and 3) point to the next node in the linked list.
If the key-value pair already points to a linked list node, then you need to delete that node and insert it using addToTail.