Dev Skills
Go·Go for coding rounds

LRU cache with container/list and a map

The design question disguised as a coding question: two structures, each covering what the other cannot.

Topic 29 of 98 · 5 min to read · 55 min to build
After this topic you can
  • Write an LRU cache with O(1) Get and Put using a map and container/list.
  • Explain why the list entry must store its key.
  • Predict which key is evicted after a sequence of calls.

The problem

Build a cache with a fixed capacity. Get(key) and Put(key, val) must both be O(1). When it is full, Put evicts the least recently used key.

Brute force first

Keep a plain slice of {key, val} pairs, most recent at the front. Get scans for the key, removes it and puts it at the front. Put does the same, and drops the last pair when the slice is full.

Every operation scans and shifts: O(capacity) time per call, O(capacity) space. Correct, but the question asks for O(1).

The approach

A map alone gives O(1) lookup but no order. A list alone gives order but O(n) lookup. Together: the map points at list nodes, and the doubly linked list keeps them in recency order. Move a node to the front on every use; evict from the back. O(1) for both operations, O(capacity) space.

Go’s container/list is that doubly linked list, so you do not write one in the interview unless asked.

lru.go
package main
import (
	"container/list"
	"fmt"
)
type entry struct {
	key, val int
}
// LRU: the map finds a node in O(1), the list keeps recency order in O(1).
// Front = most recently used, back = next to evict.
type LRU struct {
	cap   int
	ll    *list.List
	items map[int]*list.Element
}
func NewLRU(capacity int) *LRU {
	return &LRU{cap: capacity, ll: list.New(), items: map[int]*list.Element{}}
}
func (c *LRU) Get(key int) (int, bool) {
	el, ok := c.items[key]
	if !ok {
		return 0, false
	}
	c.ll.MoveToFront(el) // a read counts as a use
	return el.Value.(*entry).val, true
}
func (c *LRU) Put(key, val int) {
	if el, ok := c.items[key]; ok {
		el.Value.(*entry).val = val
		c.ll.MoveToFront(el)
		return
	}
	c.items[key] = c.ll.PushFront(&entry{key, val})
	if c.ll.Len() > c.cap {
		old := c.ll.Back()
		c.ll.Remove(old)
		delete(c.items, old.Value.(*entry).key) // why the entry stores its key
	}
}
func main() {
	c := NewLRU(2)
	c.Put(1, 1)
	c.Put(2, 2)
	fmt.Println(c.Get(1)) // 1 true   (1 is now most recent)
	c.Put(3, 3)           // evicts 2
	fmt.Println(c.Get(2)) // 0 false
	c.Put(4, 4)           // evicts 1
	fmt.Println(c.Get(1)) // 0 false
	fmt.Println(c.Get(3)) // 3 true
	fmt.Println(c.Get(4)) // 4 true
}

Dry run

Capacity 2, following the main in the program. The list is shown front (most recent) to back:

callresultlist aftermap keys
Put(1, 1)-1{1}
Put(2, 2)-2, 1{1, 2}
Get(1)1 true1, 2{1, 2}
Put(3, 3)full, evict back = 23, 1{1, 3}
Get(2)0 false3, 1{1, 3}
Put(4, 4)full, evict back = 14, 3{3, 4}

Go-specific gotchas

  • Store the key inside the list entry. On eviction you only have the list node, and you need the key to delete it from the map.
  • `list.Element.Value` is `any`. The type assertion el.Value.(*entry) is the price of a pre-generics package. Storing a pointer lets you update the value in place.
  • Not safe for concurrent use. Even Get mutates (it moves the node), so a sync.RWMutex read lock is not enough — use a plain sync.Mutex. Ask whether they want it thread-safe before adding one.
  • A `map` of pointers keeps nodes alive. Forgetting the delete on eviction is a memory leak that no test of Get will catch.
The short version
  • Map for O(1) find, doubly linked list for O(1) reorder and evict.
  • Every Get hit is a use: move to front.
  • The entry stores its key so eviction can clean up the map.
Remember: When one data structure cannot do both jobs in O(1), use two that point at each other.
Build this before moving on
Add a Peek(key) method that returns the value without making it most recent. Show with a test that a peeked key can still be evicted.
Coding challenge · checked by tests
Finish the LRU cache: NewLRU(capacity), Get(key) (int, bool) and Put(key, val). Both Get and Put make a key the most recently used; updating an existing key changes its value and refreshes it. When a Put adds a new key to a full cache, evict the least recently used key. Example with capacity 2: Put(1,1) Put(2,2) Get(1) Put(3,3) evicts 2.

Tab indents. Press Esc, then Tab, to leave the editor.

Then try these in your own editor
  1. 1The main task: Add a Peek(key) method that returns the value without making it most recent. Show with a test that a peeked key can still be evicted.
  2. 2Remove the delete(c.items, ...) line on eviction and write a test that catches it.
  3. 3After the Concurrency section: make Get and Put safe for concurrent use and explain why RLock is wrong for Get.
  4. 4Capacity 2. Run Put(1,1), Put(2,2), Put(1,10), Put(3,3). Which key is evicted, and what does Get(1) return?
  5. 5Why does the brute-force slice version cost O(n) per Get, even though finding a key in a map is O(1)? What exactly does container/list fix?
Official documentation
Check yourselfTake the Go for coding rounds test