Least Recently Used (LRU) Cache

During the interview, when asked to describe or implement an LRU Cache , the interviewer is assessing your understanding of Data Structures and Algorithms, as well as your ability to apply them to practical scenarios, particularly in the context of memory management. LRU stands for Least Recently Used , which is a type of caching algorithm. Essentially, the cache has a defined size limit, and once that limit is reached, it must make space for new entries. In an LRU cache, when space is needed, the items that have been used the least recently are the first to be removed. Important points to cover in your response: You should clarify what an LRU Cache is. You should elucidate how an LRU Cache operates.

An LRU Cache is a cache mechanism that removes the least recently used entry when it reaches its maximum capacity. The main operations of the cache include: Adding an item. This is straightforward if the cache is not full, but if it is at capacity, it necessitates the removal of a least recently used item prior to the new insertion. Retrieving an item from the cache. When an item is accessed, it is marked as the most recently used. Additionally, the cache needs to efficiently identify which item is the least recently used in order to evict it when the cache becomes full. To maintain this efficiency, an LRU cache is typically implemented using a Hashmap (allowing for O(1) insertion and retrieval) and a Doubly Linked List (which enables updating the 'recently used' status of cache entries in O(1) time).

Let's consider a practical example. Imagine we have an empty LRU cache with a capacity of 2 slots. Now, we will carry out the following operations: Insert (1,1): the cache now contains {1=1} Insert (2,2): the cache is now {1=1, 2=2} Get (1): returns 1; the cache updates to {2=2, 1=1} Insert (3,3): the least recently used key was 2, which gets evicted; the cache is now {1=1, 3=3} Get (2): returns -1 (not found) Insert (4,4): the least recently used key was 1, which gets evicted; the cache updates to {3=3, 4=4} Get (1): returns -1 (not found) This series of operations demonstrates how the LRU cache functions—items that are most recently used are retained, while those that are least recently used are removed when the cache reaches its capacity.