LRU Cache

mediumFREEDesign & Hash MapsUber DSA

Design a data structure for a Least Recently Used (LRU) cache. Support get(key) and put(key, value) in O(1) time. When capacity is exceeded, evict the least recently used item.

Input: operations as op,args separated by semicolons. Output results of get operations (-1 if not found).

Example

Input

2
put,1,1;put,2,2;get,1;put,3,3;get,2;put,4,4;get,1;get,3;get,4

Output

Reasoning

The cache is initialized with a capacity of $2$ , so it can hold up to $2$ key-value pairs.
The input operations are executed in sequence: put(1,1), put(2,2), get(1) returns $1$ , put(3,3) evicts 2 due to LRU, get(2) returns $-1$ as $2$ is no longer in the cache.
Continuing with the sequence: put(4,4) evicts 1, get(1) returns $-1$ , get(3) returns $3$ , and get(4) returns $4$ .
The output is generated by the get operations, resulting in $1$ , $-1$ , $-1$ , $3$ , $4$ .

Constraints

1 <= capacity <= 3000
0 <= key, value <= 10^4

Learn this in

Advanced Data StructuresDSA Study Plan

More from Uber DSA

Two Sumeasy Group Anagramsmedium Min Stackmedium Missing Numbereasy Rotate Imagemedium

Concept primer

Background Knowledge

The Least Recently Used (LRU) cache is a type of cache data structure that discards the least recently used items first when the cache reaches its capacity. This is a common technique used in computer science to optimize memory usage and improve performance. To understand this problem, it's essential to have a good grasp of hash maps (also known as dictionaries or associative arrays) and linked lists. A hash map is a data structure that stores key-value pairs and allows for efficient lookups, insertions, and deletions. A linked list is a data structure that consists of nodes, each of which points to the next node in the list.

The key concept in an LRU cache is the idea of recency, which refers to how recently an item was accessed. To implement an LRU cache, we need to keep track of the order in which items were accessed and evict the least recently used item when the cache is full. This requires a data structure that can efficiently insert, delete, and update items, as well as keep track of the order of access. Hash maps are ideal for storing key-value pairs, while linked lists can be used to keep track of the order of access.

In terms of theory, it's essential to understand the trade-offs between different data structures and algorithms. For example, hash maps have an average time complexity of $O(1)$ for lookups, insertions, and deletions, but can have poor performance in the worst case. Linked lists, on the other hand, have a time complexity of $O(n)$ for lookups, but can be efficient for insertions and deletions. Understanding these trade-offs is crucial for designing an efficient LRU cache.

Algorithm/Approach

The general approach to solving this problem involves combining a hash map with a linked list to create a data structure that can efficiently store key-value pairs and keep track of the order of access. The hash map will be used to store the key-value pairs, while the linked list will be used to keep track of the order of access. When a key is accessed, it will be moved to the front of the linked list, and when the cache is full, the least recently used item will be evicted from the linked list.

Step-by-Step Strategy

To implement the solution, follow these steps:

Create a hash map to store key-value pairs
Create a linked list to keep track of the order of access
When a key is accessed, move it to the front of the linked list
When a new key-value pair is added, check if the cache is full
If the cache is full, evict the least recently used item from the linked list
Update the hash map and linked list accordingly

Common Pitfalls

Some common pitfalls to watch out for when implementing an LRU cache include:

Failing to update the linked list when a key is accessed
Failing to evict the least recently used item when the cache is full
Using a data structure that is not efficient for insertions, deletions, and lookups

Time & Space Complexity

The expected time complexity for this problem is $O(1)$ for both get(key) and put(key, value) operations, since we are using a hash map and a linked list. The space complexity is $O(capacity)$ , where $capacity$ is the maximum number of items that the cache can hold. This is because we need to store all the key-value pairs in the hash map and linked list.

solution.py

Python 3.13

Test results