Learn and practice the Graphs, Tries, and Custom Data Structures patterns to solve coding interview problems.

Educative-99 in C++: Accelerate Your Coding Interview Prep

Proficiency in advanced data structures is a marker of a highly experienced engineer, and interviewers use such questions to finetune how they grade candidates. This module teaches you the use of two advanced data structures—graphs and tries—to solve relatively complex problems. To solve problems with very specific requirements that may not be handled by standard data structures, we gain experience in the advanced skill of the design, implementation, and efficient use of custom data structures.

Advanced Data Structures

# 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$ 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 \leq$ **capacity** $\leq 3000$
- $0 \leq$ **key** $\leq 10^4$
- $0 \leq$ **value** $\leq 10^5$
- At most $10^3$ calls will be made to **Set** and **Get**.







# Examples



Try to solve the LRU Cache cache problem.

Implement LRU Cache

Statement