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. Return the result as an integer.
Examples
Input:
capacity=2, ["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2]Output:
[null,null,1,null,-1]Explanation:
The operation results are [null, null, 1, null, -1].
Input:
capacity=1, ["put",5,10],["put",7,20],["get",5],["get",7]Output:
[null,null,-1,20]Explanation:
Capacity 1: put(7) evicts key 5. get(5)=-1 (evicted). get(7)=20 (still present).
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:
Keys 10,20 accessed (freq=2). Key 30 (freq=1) evicted when 40 added. get(30)=-1, get(10)=100.
Constraints
- •
0 ≤ capacity ≤ 10⁴ - •
0 ≤ key, value ≤ 10⁵