Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

LRU Cache

Explore how to implement an LRU cache with set and get functions to manage key-value pairs efficiently. Understand eviction of the least recently used items when capacity is reached and apply this custom data structure to optimize memory use.

We'll cover the following...

Statement

Implement an LRU cache class with the following functions:

  • Init(capacity): Initializes an LRU cache with the capacity size.
  • Set(key, value): Adds a new key-value pair or updates an existing key with a new value.
  • Get(key): Returns the value of the key, or −1-1 if the key does not exist.

If the number of keys has reached the cache capacity, evict the least recently used key and then add the new key.

As caches use relatively expensive, faster memory, they are not designed to store very large data sets. Whenever the cache becomes full, we need to evict some data from it. There are several caching algorithms to implement a cache eviction policy. LRU is a very simple and commonly used algorithm. The core concept of the LRU algorithm is to evict the oldest data from the cache to accommodate more data.

Constraints:

  • 1≤1 \leq capacity ≤3000\leq 3000
  • 0≤0 \leq key ≤104\leq 10^4
  • 0≤0 \leq value ≤105\leq 10^5
  • At most 2×1052 \times 10^5 calls will be made to Set and Get.

Examples

Understand the problem

Let’s take a moment to make sure you've correctly understood the problem. The quiz below helps you check if you're solving the correct problem:

Implement LRU Cache

1.

Suppose we have a cache with a capacity of 4. What is the output if we set a new pair with the following inputs?

key = 15

value = 100

A.
B.
C.

D.

1 / 3

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Note: Focus on setting the value and then getting the value.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4
5

Try it yourself

Implement your solution in ImplementLRUCache.java in the following coding playground. You'll need the provided supporting code to implement your solution.

Java
usercode > LRUCache.java
import java.util.*;
// Tip: You may use some of the code templates provided
// in the support files
// We will use a linkedlist of a pair of integers
// where the first integer will be the key
// and the second integer will be the value
class LRUCache {
	// Constructor that sets the size of the cache
	public LRUCache(int size) {
		// Write your code here
	}
	int get(int key) {
		// Replace this placeholder return statement with your code
		return -1;
	}
	void set(int key, int value) {
		// Replace this placeholder return statement with your code
		return;
	}
}
LRU Cache