LFU cache
Implement an LFU (Least-Frequently-Used) cache with the given positive capacity. get(key) returns the value or -1 if absent. put(key, value) inserts or updates; when at capacity, evict the least-frequently-used key, breaking ties by least-recently-used. Both get and put count as a use that increments the key's frequency. Given a list of operations (['put', k, v] or ['get', k]), return the list of results produced by get operations, in order (put produces no output). There are 1 to 10^4 ops; capacity is between 1 and 10^4.
run_lfu_cache(capacity: int, ops: list[list]) → list[int][2,[["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["get",3],["put",4,4],["get",1],["get",3],["get",4]]]out[1,-1,3,-1,3,4]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[2,[["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["get",3],["put",4,4],["get",1],["get",3],["get",4]]][1,-1,3,-1,3,4]not run yetsample