Interview Question:

Coding - LRU Cache (Python)

Asked at Anthropic

Problem Statement:

Design and implement an LRU (Least Recently Used) cache. It should be able to perform the following operations:

1. get(key): Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
2. put(key, value): Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Examples:

LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); print(cache.get(1)); // returns 1 cache.put(3, 3); // evicts key 2 print(cache.get(2)); // returns -1 (not found) cache.put(4, 4); // evicts key 1 print(cache.get(1)); // return -1 (uses put) print(cache.get(3)); // returns 3 print(cache.get(4)); // returns 4

Constraints:

1. All keys and values will be positive integers.
2. The get and put operations must average O(1) time complexity.

Hints:

1. Use a combination of a hash map and a doubly linked list to keep track of the items in the cache.
2. The doubly linked list should maintain the order of the items based on their usage.
3. When an item is accessed, move it to the front of the list.
4. When an item needs to be evicted, remove it from the list and delete its corresponding entry in the hash map.

Solution:

`python class Node: def init(self, key, value): self.key = key self.value = value self.prev = None self.next = None

class LRUCache: def init(self, capacity: int): self.capacity = capacity self.cache = {} self.head = Node(0, 0) self.tail = Node(0, 0) self.head.next = self.tail self.tail.prev = self.head

def get(self, key: int) -> int:
    if key in self.cache:
        node = self.cache[key]
        self._remove(node)
        self._add(node)
        return node.value
    return -1

def put(self, key: int, value: int) -> None:
    if key in self.cache:
        self._remove(self.cache[key])
    node = Node(key, value)
    self._add(node)
    self.cache[key] = node
    if len(self.cache) > self.capacity:
        lru = self.head.next
        self._remove(lru)
        del self.cache[lru.key]

def _remove(self, node):
    prev = node.prev
    next = node.next
    prev.next = next
    next.prev = prev

def _add(self, node):
    prev = self.tail.prev
    prev.next = node
    node.prev = prev
    node.next = self.tail
    self.tail.prev = node

Example usage:

cache = LRUCache(2) cache.put(1, 1) cache.put(2, 2) print(cache.get(1)) # returns 1 cache.put(3, 3) # evicts key 2 print(cache.get(2)) # returns -1 (not found) cache.put(4, 4) # evicts key 1 print(cache.get(1)) # return -1 (uses put) print(cache.get(3)) # returns 3 print(cache.get(4)) # returns 4 `

Source:

• DarkInterview: LRU Cache (Python)