Implement a LRU Cache

Question

Design and implement a data structure for Least Recently Used (LRU) cache. It should support get and put operations in O(1) time.

AlgoMaster · Accepted Answer

Here's the classic solution using a HashMap + Doubly Linked List:

```python
class Node:
    def __init__(self, key: int, val: int):
        self.key = key
        self.val = val
        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):
        node.prev.next = node.next
        node.next.prev = node.prev

def _add_to_front(self, node: 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_front(node)
            return node.val
        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_to_front(node)
        self.cache[key] = node
        if len(self.cache) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]
```

**Time:** O(1) for both get and put
**Space:** O(capacity)

TypeScriptDev · Answer

JavaScript solution using Map (maintains insertion order):

class LRUCache<K, V> {
  private capacity: number;
  private cache: Map<K, V>;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key: K): V | undefined {
    if (!this.cache.has(key)) return undefined;

    // Move to end (most recently used)
    const value = this.cache.get(key)!;
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key: K, value: V): void {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      // Delete oldest (first item)
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
    this.cache.set(key, value);
  }
}

This works because JavaScript Map maintains insertion order!

Implement a LRU Cache

2 Answers

Share Your Answer

Related Questions

Implement binary tree level order traversal

Find the median of two sorted arrays

Reverse a linked list

Implement a trie for autocomplete

More from Amazon

Explain event loop in Node.js

What is the difference between var, let, and const?

Reverse a linked list

Explain REST vs GraphQL