← Back to companies
[ OK ] Loaded —
[ INFO ]
$ cd
$ ls -lt
01
02
03
04
05
$ ls -lt
01
02
03
04
05
user@intervues:~/$
Build a cache data structure that stores key-value pairs with a fixed maximum capacity. When the cache is full and a new item needs to be added, the least recently used item should be automatically removed. The cache must support two operations:
Both operations must run in O(1) average time complexity.
LRUCache class with a constructor that accepts the maximum capacityget(key) method that returns the value or -1 if not foundput(key, value) method that adds or updates entriesget and put operations should update the recency of the accessed keyget and putExample 1:
cache = LRUCache(2) cache.put(1, 100) cache.put(2, 200) cache.get(1) // returns 100 cache.put(3, 300) // evicts key 2 cache.get(2) // returns -1 (not found) cache.get(3) // returns 300 cache.get(1) // returns 100
Example 2:
cache = LRUCache(1) cache.put(5, 50) cache.get(5) // returns 50 cache.put(7, 70) // evicts key 5 cache.get(5) // returns -1 cache.get(7) // returns 70
Example 3:
cache = LRUCache(3) cache.put(1, 10) cache.put(2, 20) cache.put(3, 30) cache.get(1) // returns 10, makes key 1 most recent cache.put(4, 40) // evicts key 2 (least recent) cache.get(2) // returns -1 cache.get(1) // returns 10 cache.get(3) // returns 30 cache.get(4) // returns 40
Hint 1: Data Structure Selection To achieve O(1) time complexity for both operations, you need a combination of two data structures: one for fast lookups and another for tracking the order of usage. Consider using a hash map (dictionary) paired with a doubly linked list. The hash map provides O(1) key lookups, while the doubly linked list allows O(1) insertion and deletion operations to maintain recency order.
Hint 2: Doubly Linked List Design Create a doubly linked list where the head represents the most recently used item and the tail represents the least recently used item. Each node should store the key-value pair. When an item is accessed or added, move it to the head. When eviction is needed, remove from the tail. The hash map should store references to the nodes in the linked list for O(1) access.
Hint 3: Operations Implementation For the
getoperation: check if the key exists in the hash map, and if so, move the corresponding node to the head of the list and return its value. For theputoperation: if the key exists, update its value and move it to the head; otherwise, create a new node at the head. If capacity is exceeded after insertion, remove the tail node and its hash map entry.
Full Solution `` Explanation:
The solution uses a doubly linked list combined with a hash map (dictionary) to achieve O(1) time complexity for both operations:
Data Structures:
- A hash map (
cache) stores key-to-node mappings for O(1) lookups- A doubly linked list maintains items in order of recency (head = most recent, tail = least recent)
- Dummy head and tail nodes simplify edge case handling
Get Operation:
- Check if the key exists in the hash map (O(1))
- If found, move the node to the head position (O(1) removal and insertion)
- Return the value
Put Operation:
- If the key exists, update its value and move to head
- If the key is new, create a node and add it to the head
- If capacity is exceeded, remove the node before the tail (least recently used) and delete its hash map entry
Time Complexity: O(1) for both
getandputoperations Space Complexity: O(capacity) to store the cache entries and node references
class Node:
"""Doubly linked list node to store cache entries."""
def __init__(self, key: int, value: int):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # Maps keys to nodes
# Dummy head and tail for easier list manipulation
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node: Node) -> None:
"""Remove a node from the linked list."""
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
def _add_to_head(self, node: Node) -> None:
"""Add a node right after the head (most recent position)."""
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def _move_to_head(self, node: Node) -> None:
"""Move an existing node to the head (mark as recently used)."""
self._remove(node)
self._add_to_head(node)
def get(self, key: int) -> int:
"""Retrieve value by key, return -1 if not found."""
if key not in self.cache:
return -1
# Move accessed node to head (most recently used)
node = self.cache[key]
self._move_to_head(node)
return node.value
def put(self, key: int, value: int) -> None:
"""Insert or update a key-value pair."""
if key in self.cache:
# Update existing key
node = self.cache[key]
node.value = value
self._move_to_head(node)
else:
# Create new node
new_node = Node(key, value)
self.cache[key] = new_node
self._add_to_head(new_node)
# Check capacity and evict if necessary
if len(self.cache) > self.capacity:
# Remove least recently used (tail's previous node)
lru_node = self.tail.prev
self._remove(lru_node)
del self.cache[lru_node.key]