Implement an LRUCache class.
Functions should include:
- LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
- int get(int key) Return the value of the key if the key exists, otherwise return -1.
- void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
Examples
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
Intuition
This question requires prior knowledge or a sympathetic interviewer. You need to understand that an LRU cache is a replacement algorithm that removes the least recently used value to make room for new value.
I think this challenge is about knowing the idioms of the language you’re working in. Since we’re using python we should know that the ordered dict class offers some of the basic functionality we’ll need.
LRU Operations:
- Get the key / Check if the key exists
- Put the key
- Delete the first added key
Our solution will be to build our cache on top of the OrderedDict class. I’ll also provide a solution without help from that class.
Complexity Analysis
- Time Complexity O(1) both for put and get since all operations with an ordered dictionary are based on hash map operations
- Space complexity : O(n)
With Ordered Dict
Python’s collections library has an ordered dictionary class that offerers an excellent jumping point for an LRU cache.
class LRUCache(collections.OrderedDict):
def __init__(self, capacity: int):
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self:
return -1
self.move_to_end(key)
return self[key]
def put(self, key: int, value: int) -> None:
if key in self:
self.move_to_end(key)
self[key] = value
if len(self) > self.capacity:
self.popitem(last=False)
From scratch
If we can’t use the ordered dict class we can implement our LRUCache with some help from KVP, Node, and Double Linked List classes.
class KeyValuePair:
def __init__(self, key, value):
self.key = key
self.value = value
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.previous = None
class DoublyLinkedList:
def __init__(self):
self.root = Node(None)
self.capacity = 0
self.root.next = self.root
self.root.previous = self.root
def unshift(self, data):
node = Node(data)
self.move_front(node)
self.capacity += 1
return node
def move_front(self, node):
if node is None:
return None
elif node.prev is not None and node.next is not None:
self.isolate(node)
node.prev = self.root
node.next = self.root.next
self.root.next.previous = node
self.root.next = node
return node
def remove_tail(self):
if self.capacity == 0:
return None
removed = self.isolate(self.root.previous)
self.capacity -= 1
return removed
@staticmethod
def isolate(node):
node.next.previous = node.previous
node.previous.next = node.next
node.next = None
node.previous = None
return node
class LRUCache:
def __init__(self, max_size=10):
if max_size <= 0:
raise Exception("LRU Cache size must be greater than 0")
self.max_size = max_size
self.list = DoublyLinkedList()
self.nodes = {}
def set(self, key, value):
node = self.nodes.get(key, None)
if node is not None:
node.data.value = value
self.list.move_front(node)
return
if self.list.capacity == self.max_size:
expired = self.list.remove_tail()
del self.nodes[expired.data.key]
self.nodes[key] = self.list.unshift(KeyValuePair(key, value))
def get(self, key):
node = self.nodes.get(key, None)
if node is None:
return None
self.list.move_front(node)
return node.data.value