LESSON 267 OF 404 · HASH TABLE

LRU Cache in Go in Go

Practice

A cache keeps a few recent results close at hand so they are quick to read again. It can only hold a limited number of entries, so when it is full it must throw one away. An LRU (Least Recently Used) cache throws away the entry that was used longest ago. Build a class LRUCache that stores integer keys with integer values.

The class keeps: capacity int, a map values map[int]int (key to value) and a slice order []int (the keys, least recently used first).

Create it: newLRUCache(capacity) makes an empty cache that holds at most capacity entries.

Methods and rules:

(cache *LRUCache) get(key int) int returns the value stored for key. A hit counts as a use: the key becomes the most recently used. If the key is not in the cache (never stored, or already evicted), return -1 and change nothing.
(cache *LRUCache) put(key int, value int) stores the value for key, and the key becomes the most recently used.
- If the key is already in the cache, replace its value. Nothing is evicted.
- If the key is new and the cache already holds capacity entries, first evict the least recently used entry (remove it from the map and from order), then store the new one.
Keep order sorted by use: the least recently used key at the front, the most recently used at the end. Every use moves the key to the end.

Tools for this language:

Go has no constructors: func newLRUCache(capacity int) *LRUCache returns a pointer to a new cache, with values: map[int]int{}.
Write a helper removeKey(key int) that finds the key in cache.order and cuts it out with append(cache.order[:i], cache.order[i+1:]...).
value, found := cache.values[key] reads a value and tells whether the key exists; cache.values[key] = value stores or replaces; delete(cache.values, key) deletes an entry; len(cache.values) counts the entries; cache.order[1:] is the slice without its first item.

This version walks over the list of keys for each operation, which is fine for learning. Interview solutions reach O(1) with a hash map plus a doubly linked list.

You start with the code that tests your class (write LRUCache above it):

func mainFunction() {
	cache := newLRUCache(2)
	cache.put(1, 10)
	cache.put(2, 20)
	fmt.Println("Get 1: " + strconv.Itoa(cache.get(1)))
	cache.put(3, 30)
	fmt.Println("Get 2: " + strconv.Itoa(cache.get(2)))
	fmt.Println("Get 3: " + strconv.Itoa(cache.get(3)))
	fmt.Println("Miss 9: " + strconv.Itoa(cache.get(9)))
	cache.put(1, 11)
	fmt.Println("Update 1: " + strconv.Itoa(cache.get(1)))
	cache.put(4, 40)
	fmt.Println("Evicted 3: " + strconv.Itoa(cache.get(3)))
	fmt.Println("Kept 1: " + strconv.Itoa(cache.get(1)))
	fmt.Println("Kept 4: " + strconv.Itoa(cache.get(4)))
	small := newLRUCache(1)
	small.put(1, 100)
	small.put(2, 200)
	fmt.Println("Small 1: " + strconv.Itoa(small.get(1)))
	fmt.Println("Small 2: " + strconv.Itoa(small.get(2)))
}

Expected output:

Get 1: 10
Get 2: -1
Get 3: 30
Miss 9: -1
Update 1: 11
Evicted 3: -1
Kept 1: 11
Kept 4: 40
Small 1: -1
Small 2: 200

Check it against the rules: Get 2 is -1 because key 2 was the least recently used when key 3 arrived (key 1 had just been read). Updating key 1 to 11 does not evict anything. With capacity 1, the second put evicts the first key.

Two structures work together: the map gives a fast lookup of the value, and order remembers which key was used when. Both must always hold the same keys.

cache.removeKey(key) then cache.order = append(cache.order, key) moves a key to the end. cache.order[0] is the least recently used key.

type LRUCache struct {
	capacity int
	values   map[int]int
	order    []int
}

func newLRUCache(capacity int) *LRUCache {
	return &LRUCache{capacity: capacity, values: map[int]int{}}
}

func (cache *LRUCache) removeKey(key int) {
	for i, current := range cache.order {
		if current == key {
			cache.order = append(cache.order[:i], cache.order[i+1:]...)
			return
		}
	}
}

func (cache *LRUCache) get(key int) int {
	value, found := cache.values[key]
	if !found {
		return -1
	}
	cache.removeKey(key)
	cache.order = append(cache.order, key)
	return value
}

func (cache *LRUCache) put(key int, value int) {
	if _, found := cache.values[key]; found {
		cache.removeKey(key)
	} else if len(cache.values) >= cache.capacity {
		evicted := cache.order[0]
		cache.order = cache.order[1:]
		delete(cache.values, evicted)
	}
	cache.values[key] = value
	cache.order = append(cache.order, key)
}

STEP 1 OF 26

Guided

Ctrl + Enter to check

LRU Cache in Go in Go

Lru Cache in Go