460. LFU Cache #

Problem #

Design and implement a data structure for  Least Frequently Used (LFU) cache.

Implement the LFUCache class:

• LFUCache(int capacity) Initializes the object with the capacity of the data structure.
• int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns 1.
• void put(int key, int value) Sets or inserts the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be evicted.

Notice that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.

Example 1:

Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Explanation
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);
lfu.put(2, 2);
lfu.get(1);      // return 1
lfu.put(3, 3);   // evicts key 2
lfu.get(2);      // return -1 (not found)
lfu.get(3);      // return 3
lfu.put(4, 4);   // evicts key 1.
lfu.get(1);      // return -1 (not found)
lfu.get(3);      // return 3
lfu.get(4);      // return 4

Constraints:

• 0 <= capacity, key, value <= 104
• At most 10^5 calls will be made to get and put.

Follow up: Could you do both operations in O(1) time complexity?

Problem Summary #

Design and implement a data structure for the Least Frequently Used (LFU) cache algorithm.

Implement the LFUCache class:

• LFUCache(int capacity) - Initializes the object with the data structure’s capacity capacity
• int get(int key) - If the key exists in the cache, get the value of the key; otherwise, return -1.
• void put(int key, int value) - If the key already exists, update its value; if the key does not exist, insert the key-value pair. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. In this problem, when there is a tie (i.e., two or more keys have the same usage frequency), the least recently used key should be removed.

Note that the “number of times an item is used” is the sum of the number of calls to the get and put functions for that item since it was inserted. The usage count is set to 0 after the corresponding item is removed.

Follow-up: Can you perform both operations in O(1) time complexity?

Solution Idea #

• This is a classic LFU interview problem. See the Chapter 3 template for a detailed explanation.

Code #

package leetcode

import "container/list"

type LFUCache struct {
	nodes    map[int]*list.Element
	lists    map[int]*list.List
	capacity int
	min      int
}

type node struct {
	key       int
	value     int
	frequency int
}

func Constructor(capacity int) LFUCache {
	return LFUCache{nodes: make(map[int]*list.Element),
		lists:    make(map[int]*list.List),
		capacity: capacity,
		min:      0,
	}
}

func (this *LFUCache) Get(key int) int {
	value, ok := this.nodes[key]
	if !ok {
		return -1
	}
	currentNode := value.Value.(*node)
	this.lists[currentNode.frequency].Remove(value)
	currentNode.frequency++
	if _, ok := this.lists[currentNode.frequency]; !ok {
		this.lists[currentNode.frequency] = list.New()
	}
	newList := this.lists[currentNode.frequency]
	newNode := newList.PushBack(currentNode)
	this.nodes[key] = newNode
	if currentNode.frequency-1 == this.min && this.lists[currentNode.frequency-1].Len() == 0 {
		this.min++
	}
	return currentNode.value
}

func (this *LFUCache) Put(key int, value int) {
	if this.capacity == 0 {
		return
	}
	if currentValue, ok := this.nodes[key]; ok {
		currentNode := currentValue.Value.(*node)
		currentNode.value = value
		this.Get(key)
		return
	}
	if this.capacity == len(this.nodes) {
		currentList := this.lists[this.min]
		frontNode := currentList.Front()
		delete(this.nodes, frontNode.Value.(*node).key)
		currentList.Remove(frontNode)
	}
	this.min = 1
	currentNode := &node{
		key:       key,
		value:     value,
		frequency: 1,
	}
	if _, ok := this.lists[1]; !ok {
		this.lists[1] = list.New()
	}
	newList := this.lists[1]
	newNode := newList.PushBack(currentNode)
	this.nodes[key] = newNode
}