Data structures problem 27 of 30

LRU cache

Data structures
Hard

Implement LRUCache(capacity) with get(key), which returns the value or -1, and put(key, value). When the cache is full, adding a new key evicts the least recently used one. Both operations should be O(1).

c = LRUCache(2)
c.put(1, "a")
c.put(2, "b")
c.get(1)        # "a"  (1 is now most recent)
c.put(3, "c")   # evicts 2
c.get(2)        # -1

Show hint

You need fast lookup by key and a fast way to move a key to the "most recent" end. collections.OrderedDict has move_to_end and popitem(last=False).

Show solution

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)

The OrderedDict keeps keys from least to most recently used. Reading or writing a key moves it to the end, and eviction removes from the front. Underneath, this is a hash map combined with a doubly linked list, which is exactly what interviewers often ask you to build by hand. Browser caches and CPU caches use the same policy.

Want a problem like this every day? See today's problem and keep a streak going.