Implementation of LRU (WIth Production level code)

Question

Accepted Answer

Implementation of LRU cache using a doubly linked list and a hash map.

LRU (Least Recently Used) cache is a data structure that stores a fixed number of items and evicts the least recently used item when the cache is full.
To implement LRU cache, we can use a doubly linked list to maintain the order of items based on their usage frequency.
We can also use a hash map to store the key-value pairs for quick access and retrieval.
When a new item is accessed, it is moved to the front of the linked list. If the cache is full, the item at the end of the linked list is evicted.
When an existing item is accessed, it is moved to the front of the linked list to indicate its recent usage.
The hash map allows constant time access to items in the cache.
Example: If the cache has a capacity of 3 and the following items are accessed in order - A, B, C, D, E, F, the cache will store E, F, and D at the end.

Top Amazon Sde1 interview questions & answers