Practice/Amazon/Leetcode 460. LFU Cache

Leetcode 460. LFU Cache

CodingMust

Problem

Design and implement a data structure for a cache that evicts entries based on access frequency. The cache should support two operations:

• get(key): Retrieve the value associated with the key if it exists in the cache, otherwise return -1. This operation increases the access frequency of the key.
• put(key, value): Insert or update the key-value pair in the cache. If the cache has reached its capacity, evict the least frequently used key before inserting the new item. If multiple keys have the same lowest frequency, evict the one that was least recently used. This operation also increases the access frequency of the key.

When a key is accessed (via get or put), its frequency counter increments. The cache must efficiently track both frequency and recency to determine which item to evict.

Requirements

1. Implement a FrequencyCache class with a constructor that takes the cache capacity
2. The get method returns the value for the given key, or -1 if not found
3. The put method inserts or updates a key-value pair
4. When at capacity, evict the least frequently used key
5. Break ties by evicting the least recently used key among items with the same frequency
6. Both operations should ideally run in O(1) average time complexity

Constraints

• 1 ≤ capacity ≤ 104
• 0 ≤ key, value ≤ 105
• At most 2 × 105 calls will be made to get and put

Examples

Example 1:

cache = FrequencyCache(2) cache.put(1, 10) // cache: \{1:10\} cache.put(2, 20) // cache: \{1:10, 2:20\} cache.get(1) // returns 10, cache: \{1:10, 2:20\}, freq(1)=2, freq(2)=1 cache.put(3, 30) // evicts key 2 (lowest frequency), cache: \{1:10, 3:30\} cache.get(2) // returns -1 (not found) cache.get(3) // returns 30 cache.get(1) // returns 10

Example 2:

cache = FrequencyCache(2) cache.put(1, 100) // cache: \{1:100\}, freq(1)=1 cache.put(2, 200) // cache: \{1:100, 2:200\}, freq(1)=1, freq(2)=1 cache.put(3, 300) // both have freq=1, evict key 1 (LRU), cache: \{2:200, 3:300\} cache.get(1) // returns -1