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.

const c = new LFUCache(2);
c.put("a", 1);
c.put("b", 2);
c.get("a");       // 1 — a's count is now 2
c.put("c", 3);    // b is evicted (lowest count)
c.get("b");       // -1

const c = new LFUCache(2);
c.put("a", 1);
c.put("b", 2);
c.put("c", 3);    // tie on count 1 — oldest ("a") loses
c.get("a");       // -1