Build a class LFUCache that evicts the least frequently used key, breaking ties by evicting the least recently used key among those with the lowest use count.
LFUCache(capacity);capacitymay be0, in which case nothing is ever stored.get(key)returns the value or-1if absent. A successfulgetincrements the key's use count and makes it the most recent.put(key, value): if the key exists, overwrite the value, increment its count and make it the most recent. Otherwise, if the cache is full, evict first (lowest count, then oldest last-use), then insert the new key with a use count of 1.
c = LFUCache(2)
c.put("a", 1) # counts: a=1
c.put("b", 2) # counts: a=1, b=1
c.get("a") # 1 counts: a=2, b=1
c.put("c", 3) # full: evict b (lowest count); c=1
c.get("b") # -1
c.get("c") # 3 counts: a=2, c=2
c.put("d", 4) # a and c tie at 2; a was used longer ago -> evict a
c.get("a") # -1
Every operation must be O(1). Scanning all keys for the minimum count on each eviction is too slow for the tests (a capacity of 10,000 with 100,000 operations).
Show hint
Group keys by their use count, keeping each group in recency order, and remember which count is currently the smallest. Think about how that smallest count can change after a get, a put of an existing key, and a put of a new key.