LFU Cache

A least frequently used (LFU) cache holds at most capacity items. When it is full and a new key arrives, it throws out the key that has been used the fewest times; if several keys tie, the one among them whose last use was longest ago goes. Build an LFUCache class:

• LFUCache(capacity) makes an empty cache. With a capacity of 0 it never stores anything.
• get(key) returns the value stored for key, or -1 if the key is not in the cache. A successful get counts as one use of the key; a miss is not a use of anything.
• put(key, value) stores value under key. If the key is already in the cache, its value is replaced and that counts as one use. If the key is new and the cache is full, first remove the key with the fewest uses (on a tie, the one whose last use was longest ago), then add the new key with a use count of 1.

A key that is removed and later put again starts over with a count of 1.

Examples

c = LFUCache(2)
c.put('a', 1)      # a: 1 use
c.put('b', 2)      # b: 1 use
c.get('a')         # returns 1     (a: 2 uses)
c.put('c', 3)      # full: b has the fewest uses and goes
c.get('b')         # returns -1
c.get('c')         # returns 3     (c: 2 uses)
c.put('d', 4)      # full: a and c have 2 uses each, a was used longer ago, so a goes
[c.get('a'), c.get('c'), c.get('d')]   # returns [-1, 3, 4]

Constraints

• 0 <= capacity <= 50,000
• Up to 250,000 calls; keys are strings or whole numbers
• Every call should take about the same time however full the cache is: searching all the keys for the one to remove is too slow.