LFU Cache
Hard · Hashing · about 35 minutes
Asked at Amazon, Google, Microsoft, Apple, Salesforce, LinkedIn, Intuit, Okta, HubSpot, Grammarly, Rivian, Sony, SAP, Quora, Gusto.
Design a Least Frequently Used (LFU) cache.
LFUCache(capacity)creates the cache.get(key)returns the key's value, or -1 if absent. A successful get counts as a use.put(key, value)updates the value if the key exists (counting as a use); otherwise inserts it with a use
count of 1. If the cache is full before inserting, first evict the key with the lowest use count; among ties, evict the least recently used one.
Both operations should run in O(1) average time. With capacity 0, nothing is ever stored.