@backstreetbrogrammer
--------------------------------------------------------------------------------
SOLUTION: Design LRU cache using custom thread-safe data structures
--------------------------------------------------------------------------------
The Least Recently Used (LRU) cache is a cache eviction algorithm that organizes elements in order of use. In LRU, as the name suggests, the element that hasn't been used for the longest time will be evicted from the cache.
LRU cache algorithm
1. Inserting (key,value) pair `put(K,V)`:
- Create a new linked list node with key, value and insert into head of linked list.
- Insert key -: node mapping into hash table.
2. Get value by key `get(K)`:
- Lookup node in hash table and return node value.
- Then update most recently used item by moving the node to front (head) of linked list.
- Hash table does NOT need to be updated.
3. Finding least recently used:
- Least recently used item will be found at the end of the linked list.
4. Eviction when cache is full:
- Remove tail of linked list.
- Get key from linked list node and remove key from hash table.
Github: github.com/backstreetbrogramm...
- Top Java Coding Interview Problems Playlist: • Top Java Coding Interv...
- Apache Spark for Java Developers Playlist: • Apache Spark for Java ...
- Upgrade to Java 21 Playlist: • Upgrade to Java 21
- Java Serialization Playlist: • Java Serialization
- Dynamic Programming Playlist: • Dynamic Programming
#java #javadevelopers #javaprogramming #javacodinginterview
Негізгі бет Ғылым және технология 55 - Design LRU cache using custom thread-safe data structures
Пікірлер: 2