LFU Cache

Explore how to implement an LFU cache that evicts the least frequently used keys efficiently. Learn to maintain usage counts and manage ties by invalidating least recently used keys, ensuring O(1) average time complexity for get and put methods in a custom data structure.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement

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

Implement the LFUCache class. Here is how it should be implemented:

LFUCache(capacity): This function initializes the object with the capacity of the data structure.
Get(key): This function gets the value of the key if it exists in the cache. Otherwise, it returns -1.
Put(key, value): This function updates the value of the key if present, or inserts the key if it’s not present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there’s a tie, that is, two or more keys have the same frequency, the least recently used key is invalidated.

To determine the least frequently used key, a UseCounter is maintained for each key in the cache. The key with the smallest UseCounter is the least frequently used key. When a key is first inserted into the cache, its UseCounter is set to 1 (due to the Put() operation). The UseCounter for a key in the cache is incremented and either a Get() or Put() operation is called on it.

The Get and Put functions should both run with an average time complexity of $O(1)$ .

Constraints:

$0 \leq$ capacity $\leq 10^4$
$0 \leq$ key $\leq 10^5$
$0 \leq$ value $\leq 10^5$
At most $2×10^3$ calls will be made to Get() and Put().

Examples

usercode > lfu_cache.go

// Definition for a Linked List node
// type Node struct {
//     key        int
//     val        int
//     useCounter int
//     next       *Node
//     prev       *Node
// }
package main
type LFUCache struct {
	
	  // Write your code here
}
// This constructor intializes the LFUCache type object
func Constructor(capacity int) LFUCache {
  	// Replace this placeholder return statement with your code
  	return LFUCache{}
}
// Get returns value for the given key
func (this *LFUCache) Get(key int) int {
  
  	// Replace this placeholder return statement with your code
  	return -1
}
// Put sets the value at a given key.
func (this *LFUCache) Put(key int, value int) {
	  // Write your code here
}

LFU Cache

LFU Cache

Statement

Examples

Understand the problem

Figure it out!

Try it yourself