Design a LRU Cache

Question

Implement a Least Recently Used cache with O(1) get and put operations. Requires combining a hash map with a doubly linked list. A Google classic.

Codemia · Accepted Answer

This problem requires implementing an LRU (Least Recently Used) cache, which means we need to efficiently track the order of item usage. The key operations are `get` and `put`, which must both run in O(1) time. To achieve this, we can use a combination of a hash map (dictionary in Python) and a doubly linked list. The hash map will store the key-value pairs for quick access, while the doubly linked list will maintain the order of usage, allowing us to quickly remove the least recently used item when capacity is reached.

1. **Data Structures**: Use a hash map to store keys and their corresponding nodes in the doubly linked list. Each node will hold the key and value. The doubly linked list allows for efficient insertion and deletion from both ends.  
2. **Initialization**: Define the capacity of the cache, and initialize the head and tail of the doubly linked list to facilitate easier node addition and removal.  
3. **Get Operation**: When retrieving a value by key:  
   - Check if the key exists in the hash map. If not, return -1.  
   - If it exists, move the corresponding node to the head of the list (marking it as most recently used) and return its value.  
4. **Put Operation**: When adding a new key-value pair:  
   - If the key already exists, update the value and move the node to the head.  
   - If it doesn't exist, check if the cache is at capacity. If it is, remove the tail node (least recently used) and delete it from the hash map.  
   - Add the new node at the head of the list and add it to the hash map.

Here is a Python implementation of the LRU Cache:

```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 = {}  # key -> Node
        self.head = Node(0, 0)  # Dummy head
        self.tail = Node(0, 0)  # Dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head

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

def _add_to_head(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

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

def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            node.value = value
            self._add_to_head(node)
        else:
            if len(self.cache) >= self.capacity:
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add_to_head(new_node)
```

The time complexity for both `get` and `put` operations is O(1) because we are using a hash map for key lookups and a doubly linked list for maintaining the order of usage. The space complexity is O(n), where n is the capacity of the cache, as we need to store n key-value pairs in the hash map and n nodes in the linked list.

1. **Cache Size Zero**: If the capacity of the cache is set to zero, any `put` operation should be ignored, and `get` operations should always return -1.  
2. **Duplicate Keys**: When inserting a key that already exists, the cache should simply update the value and move that key to the most recently used position.  
3. **Accessing Non-existing Keys**: Any `get` call with a key that isn't in the cache should return -1, ensuring that we handle lookups properly.

Design a LRU Cache

Google

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string