Implement an O(1) LRU Cache

Question

The candidate is asked to implement a Least Recently Used (LRU) Cache that operates in O(1) time complexity for both get and put operations.

Codemia · Accepted Answer

To implement an LRU Cache, we need to support two main operations: `get(key)` and `put(key, value)`. The `get` operation should return the value associated with the key if it exists, and the `put` operation should insert or update the key-value pair. The cache should evict the least recently used item when it exceeds its capacity.

To achieve O(1) time complexity, we can use a combination of a hash map and a doubly linked list. The hash map will store keys and their corresponding nodes in the linked list, allowing for quick access. The doubly linked list will maintain the order of usage, where the most recently used items are at the front and the least recently used items are at the back.

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

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

def _add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        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:
            self._remove(self.cache[key])
        node = Node(key, value)
        self.cache[key] = node
        self._add_to_head(node)
        if len(self.cache) > self.capacity:
            lru_node = self.tail.prev
            self._remove(lru_node)
            del self.cache[lru_node.key]
```

The use of a hash map allows for O(1) access to cache items, while the doubly linked list maintains the order of usage efficiently. However, this implementation has a space complexity of O(n), where n is the capacity of the cache. In a multi-threaded environment, additional synchronization mechanisms would be necessary to ensure thread safety.

Implement an O(1) LRU Cache

J.P. Morgan

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

J.P. Morgan 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