Problem Statement in English

Your task is to build a class LRUCache, that has a constant time get and put API. It also has a capacity. When that capacity is exceeded, you must evict the least recently used element from the class, and then insert the new element.

An element is considered recent if the get or put API has been called on it.

Approach

In order to make the get API constant time, we simply have to use a Map. But that’s the easy part. How do we figure out which element to evict when we’ve hit the capacity limit?

We clearly need some way to maintain track of the order in which elements come in, which can also make updates to the order in constant time. Adding new elements in an order tracking mechanism is easy - we just add them to the end. The hard part is when an element that’s fairly recent, but not the most recent, is suddenly used again. Constant time removal from the middle and insertion at the end screams one thing - Linked Lists.

In Python, we’re in luck, the collections library very kindly offers us a handy class - OrderedDict.

This is essentially a Map, that’s neatly integrated with a Linked List. This way, lookup times are still $O(1)$, and when we need to mark an element as recently used, it can hook into the Map, use the key to get access to a Double Linked List node in constant time instead of having to iterate through the Doubly Linked List to get the reference.

A Doubly Linked List makes perfect sense here as we can easily rewire the previous and next nodes together. From there it’s a simple matter to grab the last element in the Doubly Linked List, and switch its next value to be this new recently used node. So to wrap this discussion up, the Map has a generic key type, and the value is a Double Linked List node.

All constant time. The only trade off here is that increased memory consumption. But hey, you can’t have everything.

Solution in Python

from collections import OrderedDict


class LRUCache:

    def __init__(self, capacity: int):
        self.store = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key in self.store:
            self.store.move_to_end(key)
            return self.store[key]

        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.store:
            self.store[key] = value
            self.store.move_to_end(key)
        else:
            if len(self.store) < self.capacity:
                self.store[key]=value
                self.store.move_to_end(key)
            else:
                self.store.popitem(last=False)
                self.store[key]=value

Complexity

  • Time: $O(1)$
    Constant time get and put operations as specified by the question.

  • Space: $O(n)$
    Since we store at most $n$ elements in the OrderedDict.

Mistakes I Made

I don’t even want to admit this, it’s just so embarrassing. I tried using a Queue to keep track of the least recently used element, and attempted to index that Queue using another Map. Let’s just forget it happened, yea? Please, and thank you.

And we are done.