gemini-2.5-flash-preview-04-17· Google LMArena Human Preference 140K
Write an LRU cache
- User
Write an LRU cache
- Assistant
Okay, here is a Python implementation of an LRU (Least Recently Used) cache using a combination of a dictionary and a doubly linked list.
The dictionary provides O(1) average time complexity for
getandputoperations (to find the node), and the doubly linked list provides O(1) time complexity for reordering nodes (moving to head, removing from tail).class Node: """ A node for the doubly linked list to store key-value pairs and maintain the order of usage. """ def __init__(self, key, value): self.key = key self.value = value self.prev = None # Pointer to the previous node self.next = None # Pointer to the next node class LRUCache: """ Implements a Least Recently Used (LRU) cache. """ def __init__(self, capacity: int): """ Initializes the LRU cache with a given capacity. Args: capacity: The maximum number of key-value pairs the cache can hold. """ self.capacity = capacity self.cache = {} # Dictionary to store key -> node mapping # Dummy head and tail nodes for the doubly linked list. # This simplifies insertion and deletion logic at the ends. self.head = Node(0, 0) self.tail = Node(0, 0) # Link the dummy head and tail initially self.head.next = self.tail self.tail.prev = self.head def _add_node(self, node: Node): """ Helper function to add a node right after the dummy head (making it the most recently used). """ node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def _remove_node(self, node: Node): """ Helper function to remove a node from the doubly linked list. """ prev_node = node.prev next_node = node.next prev_node.next = next_node next_node.prev = prev_node def _move_to_head(self, node: Node): """ Helper function to move an existing node to the head (marking it as most recently used). """ self._remove_node(node) self._add_node(node) def _pop_tail(self) -> int: """ Helper function to remove the node just before the dummy tail (this is the least recently used node) and return its key. """ lru_node = self.tail.prev self._remove_node(lru_node) return lru_node.key def get(self, key: int) -> int: """ Retrieves the value for a given key. If the key exists, move the corresponding node to the head and return its value. Otherwise, return -1. Args: key: The key to retrieve. Returns: The value associated with the key, or -1 if the key is not found. """ if key in self.cache: node = self.cache[key] self._move_to_head(node) return node.value else: return -1 # Key not found def put(self, key: int, value: int) -> None: """ Adds or updates a key-value pair in the cache. If the key exists, update its value and move the node to the head. If the key does not exist: - Create a new node and add it to the head. - If the cache exceeds capacity, remove the least recently used node (from the tail) from both the list and the dictionary. Args: key: The key to add or update. value: The value for the key. """ if key in self.cache: # Key already exists, update value and move to head node = self.cache[key] node.value = value self._move_to_head(node) else: # Key does not exist, add new node new_node = Node(key, value) self.cache[key] = new_node self._add_node(new_node) # Check if capacity is exceeded if len(self.cache) > self.capacity: # Remove the least recently used item (from the tail) lru_key = self._pop_tail() del self.cache[lru_key] # Example Usage: # lru = LRUCache(2) # lru.put(1, 1) # cache is {1:1} # lru.put(2, 2) # cache is {1:1, 2:2} # print(lru.get(1)) # returns 1; cache is {2:2, 1:1} (1 is now MRU) # lru.put(3, 3) # evicts key 2; cache is {1:1, 3:3} # print(lru.get(2)) # returns -1 (not found) # lru.put(4, 4) # evicts key 1; cache is {3:3, 4:4} # print(lru.get(1)) # returns -1 (not found) # print(lru.get(3)) # returns 3; cache is {4:4, 3:3} (3 is now MRU) # print(lru.get(4)) # returns 4; cache is {3:3, 4:4} (4 is now MRU)
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.