LRU Cache

Design a data structure that follows the Least Recently Used (LRU) eviction policy.

Function signature

type LRUCache struct { /* fields */ }

func Constructor(capacity int) LRUCache
func (c *LRUCache) Get(key int) int
func (c *LRUCache) Put(key int, value int)

Inputs / outputs

• Constructor(capacity): initialize with capacity.
• Get(key): return value or -1 if not found; mark as most recently used.
• Put(key, value): insert or update; evict LRU if capacity exceeded.

Example

capacity = 2
Put(1,1)
Put(2,2)
Get(1) -> 1
Put(3,3) // evicts key 2
Get(2) -> -1

Constraints

• 1 <= capacity <= 100_000
• Up to 200_000 operations.

Core idea (near-solution)

Use a hash map for O(1) lookups and a doubly linked list to track recency.

Invariant: most recently used item is at the front; least recently used is at the back.

Algorithm (step-by-step)

1. Get:
   • If key missing, return -1.
   • Move node to front and return its value.
2. Put:
   • If key exists, update value and move node to front.
   • Else insert new node at front and add to map.
   • If size exceeds capacity, remove tail node and delete from map.

Correctness sketch

• Invariant: most recently used item is at the front; least recently used is at the back.
• The map provides O(1) access to list nodes.
• Moving nodes to the front preserves the most-recently-used invariant.
• Evicting from the tail removes the least-recently-used item.

Trace (hand walkthrough)

Example input:
capacity = 2
Put(1,1)
Put(2,2)
Get(1) -> 1
Put(3,3) // evicts key 2
Get(2) -> -1

Walk:
- Put(1): [1]
- Put(2): [2,1]
- Get(1)=1 -> move to front: [1,2]
- Put(3): evict 2 -> [3,1]
- Get(2)=-1 (not found)

Pitfalls to avoid

• Forgetting to update the map when moving nodes.
• Not evicting the LRU item on capacity overflow.
• Breaking the list links when removing/adding nodes.

Complexity

• Time: O(1) per operation.
• Extra space: O(capacity).

Implementation notes (Go)

• Use dummy head/tail nodes to simplify insertion and removal.
• Keep a map from key to *node for O(1) access.