Description
Weighted LRU Cache The Challenge You need to build a Weighted LRU (Least Recently Used) Cache. Every item has a specific size (weight). The cache is full when the total size reaches the limit.
Useful for systems where items are not all the same size: images, API responses, database results.
What You Need to Build get(key): Find and return the value. Return -1 if missing. put(key, value, size): Add or update an item with a specific size. Remove LRU items if needed.
Example cache = WeightedLRUCache(capacity=10) cache.put("a", 1, 3) # total = 3 cache.put("b", 2, 4) # total = 7 cache.put("c", 3, 5) # removes "a", total = 9 cache.get("a") # -1
Part 1: Simple Solution Use OrderedDict. Track current_size. Remove from front when full.
Part 2: Edge Cases Item too big for capacity, update changes size, multiple removals needed, zero size.
Part 3: Fastest Solution (O(1)) Doubly Linked List + HashMap. Remove and add nodes in O(1).
Complexity: get(): O(1) put(): O(k) amortized where k is evictions
| Feature | Standard LRU | Weighted LRU | | --- | --- | --- | | Limit Type | Count of items | Total size | | Removals | Max 1 item | Can remove many | | Best For | Same size items | Different size items |