LFU Cache
Hard · Data Structures
Implement LFUCache<K, V> (least FREQUENTLY used) with a fixed capacity of at least 1. Every key has a use count.
- get(key) returns the value or undefined. A successful get increases the key's count by 1.
- put(key, value): for an existing key, update the value and increase its count by 1. For a new key, if the cache is full, first remove the key with the SMALLEST count; if several keys share it, remove the one whose last use (get or put) is the oldest. A new key starts with count 1.
- frequency(key) returns the count of a key, or 0 if it is not stored. It does not count as a use.
The driver runLFU(capacity, ops) is already written.