Design and implement a data structure for a 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) Update the value of the key if present, or inserts the key if not already 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 is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.
To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.
When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.
The functions get and put must each run in O(1) average time complexity.
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
// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1); // cache=[1,_], cnt(1)=1
lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1); // return 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4); // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4); // return 4
// cache=[4,3], cnt(4)=2, cnt(3)=3
Constraints:
1 <= capacity <= 1040 <= key <= 1050 <= value <= 109- At most
2 * 105 calls will be made to get and put.
## Solution(Python)
```Python
# LFU cache
# Goal -> cache
# eviction policy -> least frequenctly used
# get (key) -> value
# put (key, value) updates the value if present or createds
# when cache reaches its capacity in invalidate the least frequenctlt used key before inserting new item
# in tie -<> key a == b then freq is compared
#
# sample testcase
# cnt(x)
# cache = []
# Lfu cache(2) cache = [_,_]
# p 1,1 cache = [1,_] cnt(1) = 1
# p 2,2 cache = [2,1] cnt(2) = 1, cnt(1)
# g 1 return 1
# cache = [1,2] cnt(2) = 1,cnt(1) = 2
# p 3,3 cache = [3,1] cnt(1) = 2, cnt(3) = 1
#
# g 2 return -1
# g 3 return 3 cache = [3,1] cnt(3) = 2, cnt(1) = 2
# p 4 here 1 is LRU cache = [4,3] cnt(4) = 1, cnt(3) = 2
# g 1 return -1
# g 3 cache = [3,4] cnt(4) = 1 cnt(3) = 3
# g 4 cache =[4,3] cnt(4) = 2, cnt(3) = 3
#
# > cache should maintain relative order whenever key is accessed > linkedlist cache -> least used ...most used
# > key to value,counter -> hashmap
# > lfucacheline -> tracks least recently used and at back
#
# edge cases
# eviction strategy -> pop thefront element
# cache retreieval
#
# get(key)
# # if not found return -1
# # if key found
# increment the counter
# add to cacheline
# # return from cache
#
# put
# if cursize + 1 >= size : limit exceeds
# evict the least frequenctly used cache
#
# increment the counter
# create value in cache if not found
# # insitalize counter to 1
# add to cacheline
# update cache if already found
#
# Space complexity: O(n)
# Time Complexity: O(1)
#
# Notes:
# To efficiently track two things: frequency counts and order of access within frequency group
# group nodes by frequency
# within each group maintain order of access
# Hashmap + doubly linkedlist gives O(1) time
# which leads to:
# A hahsmap -> key == value
# freqmap -> freq == dll of nodes
# in doubly linkedlist maintain nodes in lru order
# min_freq -> minimum frequency level
#
# when a node is accessed :
# remove it from the freqmap > if freqlist becomes empty it was minimum frequency , incrment min_freq
# Add the node to the frequency + 1 list
# Always add to the head of the new list
#
from collections import defaultdict
from typing import Optional
class Node:
"""Node for doubly linked list to store cache entries."""
def __init__(self, key: int, value: int) -> None:
self.key = key
self.value = value
self.freq = 1 # Frequency counter starts at 1
self.prev: Optional[Node] = None
self.next: Optional[Node] = None
class DoublyLinkedList:
"""Doubly linked list to maintain nodes with same frequency in LRU order."""
def __init__(self) -> None:
# Create dummy head and tail nodes for easier manipulation
self.head = Node(-1, -1)
self.tail = Node(-1, -1)
self.head.next = self.tail
self.tail.prev = self.head
def add_first(self, node: Node) -> None:
"""Add node right after head (most recently used position)."""
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def remove(self, node: Node) -> Node:
"""Remove a specific node from the list."""
node.next.prev = node.prev
node.prev.next = node.next
node.next = None
node.prev = None
return node
def remove_last(self) -> Node:
"""Remove and return the least recently used node (before tail)."""
return self.remove(self.tail.prev)
def is_empty(self) -> bool:
"""Check if the list is empty (only contains dummy nodes)."""
return self.head.next == self.tail
class LFUCache:
"""
Least Frequently Used (LFU) cache implementation.
Evicts least frequently used items when capacity is reached.
For items with same frequency, evicts least recently used.
"""
def __init__(self, capacity: int) -> None:
self.capacity = capacity
self.min_freq = 0 # Track minimum frequency for eviction
self.node_map: dict[int, Node] = {} # Map from key to node
self.freq_map: defaultdict[int, DoublyLinkedList] = defaultdict(DoublyLinkedList) # Map from frequency to list of nodes
def get(self, key: int) -> int:
"""
Get value for the given key.
Returns -1 if key doesn't exist.
"""
# Handle edge cases
if self.capacity == 0 or key not in self.node_map:
return -1
# Get node and update its frequency
node = self.node_map[key]
self._increment_frequency(node)
return node.value
def put(self, key: int, value: int) -> None:
"""
Insert or update key-value pair in cache.
Evicts LFU item if cache is at capacity.
"""
# Handle zero capacity
if self.capacity == 0:
return
# Update existing key
if key in self.node_map:
node = self.node_map[key]
node.value = value
self._increment_frequency(node)
return
# Evict LFU item if at capacity
if len(self.node_map) == self.capacity:
freq_list = self.freq_map[self.min_freq]
evicted_node = freq_list.remove_last()
del self.node_map[evicted_node.key]
# Add new node
node = Node(key, value)
self._add_node(node)
self.node_map[key] = node
self.min_freq = 1 # New node has frequency 1
def _increment_frequency(self, node: Node) -> None:
"""
Increment frequency of a node and move it to appropriate frequency list.
"""
freq = node.freq
freq_list = self.freq_map[freq]
# Remove node from current frequency list
freq_list.remove(node)
# Clean up empty frequency list and update min_freq if needed
if freq_list.is_empty():
del self.freq_map[freq]
if freq == self.min_freq:
self.min_freq += 1
# Increment frequency and add to new frequency list
node.freq += 1
self._add_node(node)
def _add_node(self, node: Node) -> None:
"""
Add node to the frequency list corresponding to its frequency.
"""
freq = node.freq
freq_list = self.freq_map[freq]
freq_list.add_first(node)
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key, value)
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
```