Implement LRU Cache

Try to solve the Implement Least Recently Used (LRU) cache problem.

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#

Created with Fabric.js 3.6.6 Input key value 1 1 Sample example 1 key = 1 value = 1

1 of 8

Created with Fabric.js 3.6.6 Input key value 1 1 2 2 Sample example 1 key = 2 value = 2

2 of 8

Created with Fabric.js 3.6.6 key value 1 1 2 2 3 3 Input Sample example 1 key = 3 value = 3

3 of 8

Created with Fabric.js 3.6.6 key value 1 1 2 2 3 3 4 4 Input Sample example 1 key = 4 value = 4

4 of 8

Created with Fabric.js 3.6.6 key value 2 2 3 3 4 4 5 5 Input Sample example 1 key = 5 value = 5

5 of 8

Created with Fabric.js 3.6.6 -1 Output Input key value 2 2 3 3 4 4 5 5 key = 1 Sample example 1

6 of 8

Created with Fabric.js 3.6.6 key = 3 key value 2 2 4 4 5 5 3 3 Output 3 Input Sample example 1

7 of 8

Created with Fabric.js 3.6.6 key value 4 4 5 5 3 3 2 2 2 Input Output key = 2 Sample example 1

8 of 8

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. It has the keys shown below. The keys are shown sorted by age - oldest at the top, newest at the bottom. What is the new state of the cache, if we set a new pair with the following inputs?

key = 15

value = 100

A)
B)
C)

D)

Question 1 of 30 attempted

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.

Drag and drop the cards to rearrange them in the correct sequence.

To set a pair, if the given key already exists, then we’ll update the value and move the pair to the front of the list.

If the key doesn’t exist, check whether the cache is full. If there’s the capacity to add a new pair, then add it at the front of the list.

If the cache is full, remove the LRU pair and add the pair at the front of the list.

To get a value if the given key doesn’t exist, return -1.

Else, return the corresponding value to the key and move the pair to the front of the list.

Try it yourself#

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

Python
LRU_cache.py
linked_list_node.py
linked_list.py
Input #1
Input #2
Implement LRU Cache

Custom Data Structures: Introduction

Solution: Implement LRU Cache