View on LeetCode

Approach: Key→node map plus freq→doubly linked list map; bump frequency on access, track minFreq, and on overflow evict the LRU node in the minFreq list.

Complexity: O(1) per op, O(capacity) space

go

type Node struct {
	key, val, freq int
	prev, next     *Node
}

type LFUCache struct {
	capacity, minFreq int
	cache             map[int]*Node
	freq              map[int]*Node
}

func Constructor(capacity int) LFUCache {
	return LFUCache{
		capacity: capacity,
		cache:    make(map[int]*Node, capacity),
		freq:     make(map[int]*Node),
	}
}

func (this *LFUCache) Get(key int) int {
	if node, ok := this.cache[key]; ok {
		this.increaseFreq(node)
		return node.val
	}
	return -1
}

func (this *LFUCache) Put(key int, value int) {
	if node, ok := this.cache[key]; ok {
		node.val = value
		this.increaseFreq(node)
		return
	}
	if len(this.cache) >= this.capacity {
		this.evict()
	}
	node := &Node{key: key, val: value, freq: 1}
	this.cache[key] = node
	this.addToFreq(node)
	this.minFreq = 1
}

func (this *LFUCache) increaseFreq(node *Node) {
	this.removeFromFreq(node)
	if this.freq[node.freq] == nil || this.freq[node.freq].next == this.freq[node.freq] {
		delete(this.freq, node.freq)
		if this.minFreq == node.freq {
			this.minFreq++
		}
	}
	node.freq++
	this.addToFreq(node)
}

func (this *LFUCache) addToFreq(node *Node) {
	head, ok := this.freq[node.freq]
	if !ok {
		head = &Node{}
		head.prev = head
		head.next = head
		this.freq[node.freq] = head
	}
	node.next = head.next
	node.prev = head
	head.next.prev = node
	head.next = node
}

func (this *LFUCache) removeFromFreq(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
	node.prev = nil
	node.next = nil
}

func (this *LFUCache) evict() {
	head := this.freq[this.minFreq]
	lru := head.prev
	this.removeFromFreq(lru)
	delete(this.cache, lru.key)
	if head.next == head {
		delete(this.freq, this.minFreq)
	}
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */