LRU Cache
Medium
0 views
Topics:
Linked ListsDynamic Programming
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity)Initialize the LRU cache with positive sizecapacity.int get(int key)Return the value of thekeyif the key exists, otherwise return-1.void put(int key, int value)Update the value of thekeyif thekeyexists. Otherwise, add thekey-valuepair to the cache. If the number of keys exceeds thecapacityfrom this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
Example 1:
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
Constraints:
1 <= capacity <= 30000 <= key <= 1040 <= value <= 105- At most
2 * 105calls will be made togetandput.
Solution
Clarifying Questions
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
- What is the range of possible values for the keys and values that will be stored in the cache?
- What is the expected capacity of the LRU cache? Is it safe to assume it will always be a positive integer?
- What should happen if I try to `put` a key that already exists in the cache? Should I update the value and move it to the most recently used, or treat it as an error?
- If the key is not found in the `get` operation, should I return null instead of -1, or is -1 strictly the required return value?
- Is the cache expected to be thread-safe? If so, what kind of concurrency handling should be implemented?
Brute Force Solution
Approach
A Least Recently Used (LRU) cache stores a limited number of items. The brute force approach involves checking the entire history of item usage every time we need to retrieve or store something. This ensures we always have the absolute least recently used item to discard, but it requires significant effort each time.
Here's how the algorithm would work step-by-step:
- When we want to retrieve an item, we go through every item we have stored and manually check if any of them match the item we're looking for.
- If we find a match, we return the item.
- If we don't find the item, we return 'not found'.
- When we want to store an item, we first check if the cache is full by counting how many items are currently stored.
- If the cache is not full, we simply add the new item to the cache.
- If the cache is full, we need to find the least recently used item. To do this, we examine the entire history of every action we have ever taken: adding or accessing values.
- We find the item that was used the longest time ago from the entire history.
- We remove that least recently used item to make space for the new item, and then we add the new item to the cache.
Code Implementation
class LRUCacheBruteForce:
def __init__(self, capacity):
self.capacity = capacity
self.cache_items = []
self.usage_history = []
def get(self, key):
for item in self.cache_items:
if item['key'] == key:
self.usage_history.append(key)
return item['value']
return -1
def put(self, key, value):
# Check if the cache is full
if len(self.cache_items) == self.capacity:
# Find the least recently used item
least_recent_key = self.find_least_recently_used()
# Remove the least recently used item
self.remove_item(least_recent_key)
# Add the new item to the cache
self.cache_items.append({'key': key, 'value': value})
self.usage_history.append(key)
def find_least_recently_used(self):
if not self.usage_history:
return None
key_counts = {}
for key in self.usage_history:
key_counts[key] = key_counts.get(key, 0) + 1
least_recent_key = None
least_recent_index = float('inf')
# Iterate through cache to find the least recently used.
for cache_item in self.cache_items:
try:
first_occurrence = self.usage_history.index(cache_item['key'])
except ValueError:
first_occurrence = float('inf')
if first_occurrence < least_recent_index:
least_recent_index = first_occurrence
least_recent_key = cache_item['key']
return least_recent_key
def remove_item(self, key):
# Find and remove from usage history and cache items
self.cache_items = [item for item in self.cache_items if item['key'] != key]
self.usage_history = [k for k in self.usage_history if k != key]
Big(O) Analysis
Time Complexity
O(n) – The get operation iterates through all n elements in the cache to find a key, resulting in O(n) complexity. The put operation involves checking for cache fullness (O(1)), finding the least recently used item by examining a history of potentially n actions (O(n) to find the least recently used), and potentially removing/adding an item (O(1)). Since finding the least recently used item dominates when the cache is full, the put operation is also O(n). Therefore, the overall time complexity is O(n) for both get and put.
Space Complexity
O(1) – The brute force approach described requires only a fixed number of variables to keep track of the cache's capacity and potentially a counter for iterating through the cache. No auxiliary data structures like lists, hash maps, or trees are created to store the history of accesses or cached items beyond the cache itself. Therefore, the auxiliary space used remains constant regardless of the cache size N. The algorithm's memory usage does not scale with the number of operations or the size of the data stored.
Optimal Solution
Approach
The challenge is to create a memory system that quickly remembers the most recently used items while forgetting the least used. The optimal approach combines a way to quickly find an item (like a dictionary) and a way to keep track of how recently things were used (like a line of people waiting).
Here's how the algorithm would work step-by-step:
- Use a system that lets you instantly find the item you're looking for, like using a key to open a specific locker.
- Use a 'line' to represent how recently items were used. The most recently used item goes to the front of the line.
- When you use an item, move it to the front of the line.
- If the memory is full and you need to add a new item, remove the item at the back of the line (the least recently used) to make space.
- Keep your 'line' and your 'locker' system in sync so you always know where to find things and what's been used most recently.
- This ensures that accessing, adding, and removing items happens very quickly, as you're not searching through everything, just adjusting the 'line' and 'locker'.
Code Implementation
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
self.prev = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {}
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
# Remove node from linked list
node.prev.next = node.next
node.next.prev = node.prev
def _add(self, node):
# Add node to the head of linked list
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key in self.cache:
node = self.cache[key]
self._remove(node)
self._add(node)
return node.value
return -1
def put(self, key, value):
if key in self.cache:
# If key exists, update and move to front
node = self.cache[key]
node.value = value
self._remove(node)
self._add(node)
else:
# Need to add a new node
new_node = Node(key, value)
self.cache[key] = new_node
self._add(new_node)
if len(self.cache) > self.capacity:
# Remove the least recently used node
tail_node = self.tail.prev
self._remove(tail_node)
del self.cache[tail_node.key]
Big(O) Analysis
Time Complexity
O(1) – The LRU cache implementation uses a hash map (dictionary) for O(1) average-case time complexity for get and put operations. The doubly linked list operations for maintaining the order of recent use, such as moving a node to the head or removing the tail, also take O(1) time. Therefore, both get and put have constant time complexity, independent of the number of items stored (n). Thus, the time complexity of the described LRU cache operations is O(1).
Space Complexity
O(capacity) – The LRU cache implementation utilizes a dictionary (hash map) to store key-value pairs for quick access and a doubly linked list to maintain the order of recently used items. The dictionary stores references to the nodes in the linked list. Both the dictionary and the linked list can grow up to the cache's capacity. Therefore, the auxiliary space used is proportional to the capacity of the cache, leading to a space complexity of O(capacity), where capacity is the maximum number of items the cache can hold.
Edge Cases
| Case | How to Handle |
|---|---|
| Cache capacity is zero | Disallow creation of cache with capacity zero or throw exception, since it cannot store any elements. |
| Inserting the same key multiple times with different values | The `put` operation should update the existing key's value and move it to the most recently used position. |
| Getting a key that doesn't exist | The `get` operation must return -1 without modifying the cache state. |
| Cache is full and we try to put a new key | The least recently used key should be evicted before adding the new key-value pair. |
| Cache is empty and we call get() | Get should return -1 if the cache is empty. |
| Large number of get() and put() operations | Ensure the data structure scales efficiently (O(1) for both operations) even with a large number of operations, and avoids memory leaks. |
| Integer overflow when handling key or value | Consider using long data type instead of int if keys or values might exceed integer limits. |
| Evicting the head or tail of the doubly linked list | Ensure the head and tail pointers are correctly updated when evicting either the head or tail of the linked list. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
