LRU Cache

Medium

The problem

Build an LRUCache (least recently used cache) with a fixed capacity. Get(key) returns the value for the key, or -1 if it is not there. Put(key, value) stores a value (replacing the old one if the key exists). When storing would make the cache hold more than capacity keys, remove the key that was used least recently. Both Get and Put count as "using" a key. Each call should run in constant time.

Example 1
Input: c := Constructor(2) c.Put(1, 10) c.Put(2, 20) c.Get(1) // 10 c.Put(3, 30) c.Get(2) // -1 c.Put(4, 40) c.Get(1) // -1 c.Get(3) // 30 c.Get(4) // 40
Output: Get results in order: 10, -1, -1, 30, 40
After Get(1), key 2 is the least recently used, so Put(3, 30) throws out key 2. Then key 1 is the oldest, so Put(4, 40) throws out key 1. Keys 3 and 4 remain.

Limits

1 ≤ capacity ≤ 3,000
0 ≤ key, value ≤ 10,000
Up to 200,000 calls in total

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

You need O(1) lookup AND O(1) "move this to most-recent / evict the oldest".

The idea

Hash map key → node of a doubly linked list. On get/put move the node to the front; when over capacity remove the tail node and its map entry.

Target: O(1) per operation

Go function shape

type LRUCache struct{}
func Constructor(capacity int) LRUCache
func (c *LRUCache) Get(key int) int
func (c *LRUCache) Put(key int, value int)

Reference solution

Tested with go test. Try it yourself first, then compare.

// LRUCache evicts the least recently used key. A hash map finds a key in O(1); a doubly linked list keeps
// keys in recency order (front = most recent) so moving or removing a node is O(1) too.
type LRUCache struct {
	cap        int
	nodes      map[int]*lruNode
	head, tail *lruNode // sentinels: head.next is the most recent, tail.prev the least recent
}
type lruNode struct {
	key, val   int
	prev, next *lruNode
}

func NewLRUCache(capacity int) *LRUCache {
	c := &LRUCache{cap: capacity, nodes: map[int]*lruNode{}, head: &lruNode{}, tail: &lruNode{}}
	c.head.next, c.tail.prev = c.tail, c.head
	return c
}

func (c *LRUCache) remove(n *lruNode) { n.prev.next, n.next.prev = n.next, n.prev }
func (c *LRUCache) pushFront(n *lruNode) {
	n.next, n.prev = c.head.next, c.head
	c.head.next.prev = n
	c.head.next = n
}

func (c *LRUCache) Get(key int) int {
	n, ok := c.nodes[key]
	if !ok {
		return -1
	}
	c.remove(n)
	c.pushFront(n) // using a key makes it the most recent
	return n.val
}

func (c *LRUCache) Put(key, val int) {
	if n, ok := c.nodes[key]; ok {
		n.val = val
		c.remove(n)
		c.pushFront(n)
		return
	}
	if len(c.nodes) == c.cap {
		lru := c.tail.prev
		c.remove(lru)
		delete(c.nodes, lru.key)
	}
	n := &lruNode{key: key, val: val}
	c.nodes[key] = n
	c.pushFront(n)
}

Read the lesson: Linked List · Fast & Slow Pointers