55 - Design LRU cache using custom thread-safe data structures

Показать описание

@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.

#java #javadevelopers #javaprogramming #javacodinginterview

Rishi Srivastava

Рекомендации по теме

Комментарии

I think there is a race condition here.
The get operation is not a simple read operation - it's doing modifications in our DLL. And since we're only taking a read lock in the get op, multiple get ops might concurrently modifiy the DLL.
For eg., if multiple threads try to put a node at the head of the DLL at the same time, how do we make sure their pointers are all properly updated?

abhicsmnnit

55 - Design LRU cache using custom thread-safe data structures

55 - Design LRU cache using custom thread-safe data structures

Implement LRU cache

Design LRU Cache Data Sturcture | LeetCode 146. LRU Cache | Least Recently Used Cache (LRU Cache)

Low Level Design (LRU Cache) || System Design Principles

System Design - (P-1) - Java LRU Cache Implementation | Step-by-Step Tutorial with High-Level Design

Master Java's LinkedHashMap with this LRU Cache Implementation - LeetCode 146. LRU Cache

LRU cache | Leetcode #146

Implement LRU Cache | Implement LRU Cache using HashMap & Doubly Linked List | Programming Tutor...

Implement LRU Cache | SWE Interview #19

Lecture 17: What is LRU Cache? | SPG | JAVA

LRU Cache - LeetCode #146 - C++

What is LRU cache?

LeetCode Quick Review Vlog: Problem 146 - LRU Cache

LRU Cache Replacement Policy - Solved PYQs

Ace Algorithms and Programming Interviews in Swift : LRU Cache

12.8 LRU CACHE (Heaps and Maps)-Interviewbit #heap#map#interview

LRU Cache | Leetcode 146 | Interview Prep | Python

LeetCode - 146. LRU Cache | Java

LeetCode in Java - LRU Cache

Linked List LRU Cache - Complexity Analysis

Leaking Information Through Cache LRU States in Commercial Processors and Secure Caches (0421)

[Java] Leetcode 460. LFU Cache [Design #4]

Python Tutorial - || Memoization || LRU Cache || Code Walk-through ||

LRU Cache - Doubly Linked List, Set - inDepth - Beat My Score