Categories
interviews

Implement LRU Cache in Python

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.

Table Of Contents
  1. LRU cache
  2. Using Python OrderedDict as LRU cache
  3. Implement LRU cache using doubly linked list
  4. Summary

LRU cache

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 get and 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 list, deque or 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 move_to_end and popitem(last=False) methods to achieve efficient get and 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.

To see another great implementation see Dmitry Babichev‘s solution.

Summary

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:

Cracking the Coding Interview: 189 Programming Questions and Solutions 6th Edition on Amazon.