To deviate a bit from my usual DevOps articles, I’ll show my attempts to implement LRU cache in Python. We’ll see 2 methods: one using Python built-in
OrderedDict class. The second will use custom doubly linked list implementation. If you later find this article useful take a look at the disclaimer for information on how to thank me.
Implementing LRU cache is one of the most famous interview questions. It’s even featured on Cracking the Coding Interview classic interviews book.
If you want to refresh your memory of what LRU cache means, there’s a great article on Wikipedia.
To scope and define a problem, I’ll use Leetcode’s problem definition.
The most important requirement is that cache
put operations must each run in
O(1) average time complexity. It’s also important to remember that both these operations affect the least recently used item in the cache (
put in case it’s an update of an existing item).
Implementations using python
dict as the underlying cache data structure suffer from either underlying inefficiencies (not O(1)) or lack of
LRU order. Luckily there’s Python built in data structure –
OrderedDict which implements both requirements out of the box.
Using Python OrderedDict as LRU cache
Below implementation uses OrderedDict as an underlying data structure. It uses
popitem(last=False) methods to achieve efficient
put of the LRU cache.
from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.cap = capacity self.cache = OrderedDict() def get(self, key: int) -> int: if key in self.cache: self.cache.move_to_end(key) return self.cache[key] return -1 def put(self, key: int, value: int) -> None: if key not in self.cache: if len(self.cache) == self.cap: self.cache.popitem(last=False) self.cache[key] = value else: self.cache.move_to_end(key) self.cache[key] = value
Implement LRU cache using doubly linked list
While using built in Python classes is nice to have knowledge, interviewers may require to implement LRU cache using custom classes. Below implementation uses doubly linked list custom implementation along with a dictionary. The list holds the nodes with keys and values. Dictionary holds the mapping between the keys and list nodes. List head is LRU node, its tail is MRU node. Once an existing key is accessed using
get or updated using
put, its node becomes a list’s tail. The dictionary allows O(1) random access to the node. You can find the implementation below:
from collections import OrderedDict class DLNode: def __init__(self, key, value): self.key = key self.val = value self.next = None self.prev = None class DLList: def __init__(self): self.head = None self.tail = None def append(self, node): if not self.head and not self.tail: self.head = node self.tail = node else: self.tail.prev = node node.next = self.tail self.tail = node def pophead(self): if self.head: old_head = self.head self.head = old_head.prev if self.head: self.head.next = None old_head.prev = None else: self.tail = None return old_head return None def move_to_end(self, node): if self.tail == node and self.head == node: return # disconnect node from its prev and next nn = node.next np = node.prev if nn: nn.prev = np if np: np.next = nn else: self.tail = nn else: self.head = np if np: np.next = None else: self.tail = None # move node to tail node.next = self.tail self.tail.prev = node node.prev = None self.tail = node class LRUCache: def __init__(self, capacity: int): self.cap = capacity self.values = DLList() self.keys = dict() def get(self, key: int) -> int: if key in self.keys: node = self.keys[key] self.values.move_to_end(node) return node.val return -1 def put(self, key: int, value: int) -> None: if key not in self.keys: if len(self.keys) == self.cap: head = self.values.pophead() del self.keys[head.key] new_node = DLNode(key, value) self.values.append(new_node) self.keys[key] = new_node else: node = self.keys[key] node.val = value self.values.move_to_end(node)
You can see and fork the implementation on my GitHub.
That’s it about implementing LRU cache in Python. As always, feel free to share.
If you found this article useful, take a look at the disclaimer for information on how to thank me.
You may also find below articles interesting: