Practice/Snapchat/Leetcode 146. LRU Cache

Leetcode 146. LRU Cache

CodingMust

Problem

Design and implement a data structure for a Least Frequently Used (LFU) cache. The cache should support retrieving items and inserting/updating items, with automatic eviction of the least frequently used item when the capacity is exceeded.

Your implementation should provide a class LFUCache with the following operations:

• LFUCache(capacity): Initialize the cache with a positive integer capacity
• get(key): Retrieve the value associated with the key if it exists in the cache, otherwise return -1. Each get operation increases the access frequency of the key.
• put(key, value): Insert or update the value for the given key. If the key already exists, update its value and increase its frequency. If the cache is at capacity and a new key needs to be inserted, evict the least frequently used key. If there is a tie in frequency, evict the least recently used among them.

Requirements

1. Both get and put operations must run in O(1) average time complexity
2. When the cache reaches capacity and a new key must be inserted, evict the key with the lowest access frequency
3. If multiple keys share the same lowest frequency, evict the one that was least recently used (oldest in time)
4. Every successful get operation increments the access frequency of that key
5. When a key is updated via put, its frequency is incremented (not reset)

Constraints

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

Examples

Example 1:

LFUCache cache = new LFUCache(2); cache.put(1, 100); // cache=\{1=100\} cache.put(2, 200); // cache=\{1=100, 2=200\} cache.get(1); // returns 100, cache=\{1=100, 2=200\}, freq(1)=1 cache.put(3, 300); // evicts key 2, cache=\{1=100, 3=300\} cache.get(2); // returns -1 (not found) cache.get(3); // returns 300, freq(3)=1 cache.put(4, 400); // evicts key 1 (freq 1, older than key 3), cache=\{3=300, 4=400\} cache.get(1); // returns -1 (not found) cache.get(3); // returns 300 cache.get(4); // returns 400

Example 2:

LFUCache cache = new LFUCache(3); cache.put(1, 10); cache.put(2, 20); cache.put(3, 30); cache.get(1); // returns 10, freq(1)=1 cache.get(1); // returns 10, freq(1)=2 cache.put(4, 40); // evicts key 2 or 3 (both have freq 0), cache has keys \{1, 3 or 4, 4 or 3\}