How do you design an LRU (Least Recently Used) cache with strict O(1) Get and Put operations?

Short answer

Combine two data structures: a Hash Map for immediate O(1) lookup and a Doubly Linked List to track usage order and add or remove elements in O(1).

Explanation

The Hash Map stores each key and a direct reference to its node in the doubly linked list. The list has dummy Head and Tail nodes. On get(key) or when updating a value, find the node in the map and move it to the list's beginning (most recently used). When the capacity is full and put() is called, remove the node directly before the tail (least recently used) and delete it from the map in constant O(1) time.

Code example

class LRUCache {
  private map = new Map<string, Node>();
  private head = new Node('', 0);
  private tail = new Node('', 0);
  // Link Head to Tail and move on each access
}

Common mistakes

• Using a regular array and shifting the other elements to update an item's position, making each update O(N) and defeating the cache's speed.

Follow-up questions

• Why are arrays faster to iterate over than linked lists even when both have O(N) time complexity?

Sources

• LRU cache implementation - Wikipedia