filmov
tv
Implement An LRU Cache - The LRU Cache Eviction Policy ('LRU Cache' on LeetCode)
Показать описание
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Implement an LRU Cache.
It is a cache replacement policy that says to evict the least recently used item in the cache.
Every time an item is used it goes to the "front" of the cache since it has been used and has priority.
Items that are not used will go to the "end" of the cache eventually and get evicted since they are the least used items, they never got a bump up by being used.
What is a Cache?
A cache is a hardware or software component that stores data so that future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation or a copy of data stored elsewhere.
What Is An LRU Cache?
So a LRU Cache is a storage of items so that future access to those items can be serviced quickly and an LRU policy is used for cache eviction.
The Constraints/Operations
Lookup of cache items must be O(1)
Addition to the cache must be O(1)
The cache should evict items using the LRU policy
The Approach
There are many ways to do this but the most common approach is to use 2 critical structures: a doubly linked list and a hashtable.
Our Structures
Doubly Linked List: This will hold the items that our cache has. We will have n items in the cache.
This structure satisfies the constraint for fast addition since any doubly linked list item can be added or removed in O(1) time with proper references.
Hashtable: The hashtable will give us fast access to any item in the doubly linked list items to avoid O(n) search for items and the LRU entry (which will always be at the tail of the doubly linked list).
This is a very common pattern, we use a structure to satisfy special insertion or remove properties (use a BST, linked list, etc.) and back it up with with a hashtable so we do not re-traverse the structures every time to find elements.
Complexities
Time
Both get and put methods are O( 1 ) in time complexity.
Space
We use O( n ) space since we will store n items where n ist the capacity of the cache.
++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 13.3 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
0:12:25
Implement LRU cache
0:17:49
LRU Cache - Twitch Interview Question - Leetcode 146
0:13:31
Implement An LRU Cache - The LRU Cache Eviction Policy ('LRU Cache' on LeetCode)
0:24:56
L18. Implement LRU Cache
0:17:05
Implement LRU Cache | Leetcode
0:23:41
LRU Cache - Explanation, Java Implementation and Demo
0:18:47
LRU Cache Implementation | Codewise explanation using Queue & Map | Java Code
0:18:00
LeetCode 146. LRU Cache (Algorithm Explained)
0:14:45
LFU Cache - Leetcode 460 - Python
0:40:32
LRU Cache | Brute Force | Optimal | Detailed | Leetcode 146
0:23:43
Implement LRU Cache | Implement LRU Cache using HashMap & Doubly Linked List | Programming Tutor...
0:06:33
LRU cache | Leetcode #146
0:10:02
Implement LRU cache with example
0:44:30
Pro vs. Hard Coding Interview Problem - LRU Cache (LeetCode Day 24)
0:02:37
Linked List as Design Choice for LRU Cache
0:07:08
Implementing LRU Cache using LinkedHashMap in Java
0:11:20
How “lru_cache” Can Make Your Functions Over 100X FASTER In Python
![[Java] Leetcode 146.](https://i.ytimg.com/vi/WB1fRBeIxU0/hqdefault.jpg)
0:16:32
[Java] Leetcode 146. LRU Cache [Design #1]
0:08:58
L-3.13: LRU (Least Recently Used) Cache Replacement Algorithm | Computer Organisation & Architec...
0:05:12
Implementing LRU - Georgia Tech HPCA Part 3
0:11:14
LRU Cache Implementation Explained Step-By-Step
0:09:00
#1 Coding Interview Question: LRU Cache Implementation(Logicmojo.com)
0:41:38
Implement LRU Cache | Explanation + Code | Optimized Code | Doubly LL + HashMap Approach
0:08:45
What is LRU cache?
Комментарии