An LFU cache that evicts the least used

An LRU cache throws away whatever was touched longest ago, which is wrong when one big scan pushes out the handful of entries the app reads constantly. An LFU cache counts uses instead and evicts the least frequently used key.

Implement an LFUCache class. new LFUCache(capacity) takes a positive integer capacity and starts empty. get(key) returns the stored value, or -1 when the key is absent; a successful get counts as one use. put(key, value) stores a value; storing a value under a key that already exists updates it and counts as one use. size() returns how many entries are currently stored, never more than the capacity.

Every key carries a use count that starts at 1 when it is first inserted and increases by one on every get and on every put that updates it. When a put would exceed the capacity, evict the key with the lowest use count. If several keys tie on the lowest count, evict the one among them that was least recently used.

What it has to do

• get returns -1 for a missing key and counts as a use for a present one.
• Inserting past the capacity evicts the key with the lowest use count.
• Ties on the lowest use count are broken by evicting the least recently used of them.
• A put that updates an existing key counts as a use and does not evict anything.
• size() never exceeds the capacity.

Your workspace