Solution: LRU Cache

Let's solve the LRU Cache problem using the Custom Data Structures pattern.

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 10310^3 calls will be made to Set and Get.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.