Design an LRU Cache

Caching is critical in systems design, from web browsers to database engines. An LRU (Least Recently Used) cache evicts the least recently used entry when full, ensuring hot data stays accessible. Implementing one in code tests your mastery of linked lists, hash maps, and constant-time operations.

Problem Statement

Implement an LRU Cache class with these operations:

• LRUCache(int capacity): Initialize the cache with given positive capacity.

• int get(int key): Return the value of the key if it exists; otherwise return -1.

• void put(int key, int value): Insert or update the key with the value. If inserting causes capacity to exceed, evict the least recently used item.

All operations must run in O(1) time.

1. Clarify Requirements Before Jumping Into Code

I need to confirm:

• Capacity is positive and fixed.

• get of a non-existent key returns -1.

• put updates recency even if key already exists.

• Eviction happens only on inserts, not on updates.

• All ops must be worst-case O(1).

2. Identify the Category of the Question

This is a design problem combining data structures for for O(1) key lookup and another data structure for O(1) recency updates and eviction. Common patterns:

• Combining map + linked list for ordered caches

• Using head/tail pointers to represent MRU/LRU ends

• Moving accessed nodes to the head

3. Consider a Brute-Force Approach to Understand the Problem

One option for the Brute Force solution: store items in an ArrayList, then use a linear search for get and recency update:

• get: scan list O(n)

• put: scan for key O(n), remove if exists, append, evict first if full

But that’s O(n) per operation, which is too slow.

4. Brainstorm More Solutions

There isn't a single basic data structure that is able to perform all of the functions of an LRU. So my first thought is, can I combine data structures in some way to get me what I need?

To figure out what data structures I need, let me break up the problem into two questions:

1. What data structure would allow me to have constant time get and update?

2. What data structure would allow me to update the ordering of elements in constant time?
   

Constant time get and update operations immediately brings to mind hash structures like a hash map or hash set. But since hash maps/sets can't maintain ordering, I also know we will need to combine a map/set with another data structure. Knowing that I will need to maintain references between two different data structures makes me think that a hash map is my best bet.

Now I need to figure out which data structure will allow me to update the ordering in constant time. Min/Max Heaps give me the ordering I need, but maintaining that ordering in a heap is an O(log n) operation. An Array would require me to update the whole list to shift elements up/down when they are accessed, so that's off the table.

What about a linked list?

• With a linked list, moving nodes around can be done in constant time, since all I need to do is update pointers.

• To update pointers, I need to know the node that proceeds my updated node, as well as the node that follows - that suggests I need a doubly linked list.

• To maintain ordering, when a node is accessed, all I need to do is move it to the front of the list (or the back if you want to the reverse ordering, doesn't make a difference).

• A hash map that maps a key to its corresponding node would allow me to jump immediately to the linked list node that needs to be updated.

• And when I need to evict the least-recently used element, I just drop the last element in the linked list!

This looks right! My optimal solution is one where I can combine a hash map with a doubly linked list to achieve constant time get and update!

To recap:

Maintain a doubly linked list of entries in recency order plus a hash map from key→node. On get, if found, move node to head.

On put, if key exists update value and move head; else insert new node at head, update map, and if over capacity remove tail node.

5. Discuss Trade-Offs Between Your Solutions

Approach	get	put	Space	Pros	Cons
ArrayList + linear operations	O(n)	O(n)	O(n)	Simple	Too slow
LinkedHashMap (built-in)	O(1)	O(1)	O(n)	Minimal code	Doesn’t show algorithmic skill
HashMap + doubly linked list	O(1)	O(1)	O(n) + O(n)	True O(1), clear mechanics	More code to write

6. Write Pseudocode to Structure Your Thoughts

initialize map and empty DLL with dummy head & tail
function get(key):
  if key not in map: return -1
  node = map[key]
  remove node from list
  insert node at head
  return node.value

function put(key, value):
  if key in map:
    node = map[key]
    node.value = value
    remove node from list
    insert node at head
  else:
    node = new Node(key, value)
    map[key] = node
    insert node at head
    if map.size > capacity:
      lru = tail.prev
      remove lru from list
      remove lru.key from map

7. Consider Edge Cases

• Capacity = 1 (evict immediately on every new insert).

• Repeated put of same key visits update path.

• get before any put returns -1.

• Large number of operations should still be O(1) each.

8. Write Full Code Syntax (Java)

import java.util.HashMap;

class LRUCache {
    private class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) { key = k; value = v; }
    }

    private final int capacity;
    private HashMap<Integer, Node> map;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(0, 0); // dummy
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        remove(node);
        insertAtHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            remove(node);
            insertAtHead(node);
        } else {
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            insertAtHead(newNode);
            if (map.size() > capacity) {
                Node lru = tail.prev;
                remove(lru);
                map.remove(lru.key);
            }
        }
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void insertAtHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

9. Test Your Code

public static void main(String[] args) {
    LRUCache cache = new LRUCache(2);

    System.out.println(cache.get(1) == -1);

    cache.put(1, 1);
    cache.put(2, 2);
    System.out.println(cache.get(1) == 1); // returns 1

    cache.put(3, 3);                      // evicts key 2
    System.out.println(cache.get(2) == -1);

    cache.put(4, 4);                      // evicts key 1
    System.out.println(cache.get(1) == -1);
    System.out.println(cache.get(3) == 3);
    System.out.println(cache.get(4) == 4);

    // capacity = 1
    LRUCache single = new LRUCache(1);
    single.put(10, 10);
    System.out.println(single.get(10) == 10);
    single.put(20, 20);
    System.out.println(single.get(10) == -1);
    System.out.println(single.get(20) == 20);
}

10. Key Lessons to Remember for Future Questions

• Combining a hash map and doubly linked list yields O(1) access and recency updates.

• Keep recency list operations in helper methods (remove, insertAtHead) for clarity.

Good luck and happy coding!