LRU Cache Design Problem Statement

Design a data structure that implements a Least Recently Used (LRU) cache. The cache should support the following operations: get(key) and put(key, value).

When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

Follow these constraints:

get should return the value of the key if the key exists in the cache. Otherwise, it should return -1.

put should update the value of the key if the key exists. Otherwise, it should insert the key-value pair. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

Example:

LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

Question

LRU Cache Design Problem Statement

Design a data structure that implements a Least Recently Used (LRU) cache. The cache should support the following operations: get(key) and put(key, value).

When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

Follow these constraints:

get should return the value of the key if the key exists in the cache. Otherwise, it should return -1.
put should update the value of the key if the key exists. Otherwise, it should insert the key-value pair. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

Example:

 LRUCache cache = new LRUCache(2); 
 cache.put(1, 1); 
 cache.put(2, 2); 
 cache.get(1);       // returns 1 
 cache.put(3, 3);    // evicts key 2 
 cache.get(2);       // returns -1 (not found) 
 cache.put(4, 4);    // evicts key 1 
 cache.get(1);       // returns -1 (not found) 
 cache.get(3);       // returns 3 
 cache.get(4);       // returns 4

Accepted Answer

Implementing an LRU Cache involves using a data structure to store key-value pairs with a limit on size, evicting the least recently used.

Use a combination of a hash map and a doubly linked list for efficient access and updates.
The hash map stores keys and pointers to the corresponding nodes in the linked list.
The linked list maintains the order of usage, with the most recently used at the head and least recently used at the tail.
When adding a new item, if the cache exceeds its capacity, remove the tail node (least recently used).
Example: For a cache of size 2, adding (1,1) and (2,2) then accessing 1, and adding (3,3) results in cache containing (1,1) and (3,3).

Asked in Oracle and 21 others

Interview Questions from Popular Companies