Description
Design and implement a data structure for a Least Frequently Used (LFU) cache. When capacity is reached, invalidate the least frequently used key before inserting a new item.
Examples
Input:
capacity=2, ["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2]Output:
[null,null,1,null,-1]Explanation:
Key 2 had lower frequency than key 1, so it was evicted.
Input:
capacity=1, ["put",5,10],["put",7,20],["get",5],["get",7]Output:
[null,null,-1,20]Explanation:
With capacity 1, when key 7 is inserted, key 5 is immediately evicted since there's no room. Getting key 5 returns -1 (not found), while getting key 7 returns 20 (the stored value).
Input:
capacity=3, ["put",10,100],["put",20,200],["put",30,300],["get",10],["get",20],["put",40,400],["get",30],["get",10]Output:
[null,null,null,100,200,null,-1,100]Explanation:
All keys start with frequency 1. After getting keys 10 and 20, they have frequency 2 while key 30 still has frequency 1. When key 40 is added and capacity is exceeded, key 30 (least frequent) is evicted. Getting key 30 returns -1, but key 10 returns 100.
Constraints
- •
0 ≤ capacity ≤ 10⁴ - •
0 ≤ key, value ≤ 10⁵