Practice/xAI/Weighted LRU Cache

Weighted LRU Cache

CodingMust

Problem Overview

Design and implement a Weighted LRU (Least Recently Used) Cache that extends the traditional LRU cache by assigning a size (or weight) to each item. Unlike a standard LRU cache where each item counts as 1 toward the capacity, in a weighted LRU cache, the capacity is calculated as the sum of all item sizes.

This variant is commonly used in systems where cached items have varying memory footprints, such as:

• Image caching (different resolutions have different file sizes)
• API response caching (responses vary in payload size)
• Database query result caching (result sets have different row counts)
• LLM KV cache management (different prompt lengths require different memory)

Part 1: Basic Implementation

Implement a WeightedLRUCache class with get and put operations.

Example

`

Capacity is 10 (total weight, not item count)

cache = WeightedLRUCache(capacity=10)

cache.put("a", 1, 3) # Cache: {"a": (1, size=3)} -> total size = 3 cache.put("b", 2, 4) # Cache: {"a": (1, 3), "b": (2, 4)} -> total size = 7 cache.put("c", 3, 5) # Exceeds capacity (7 + 5 = 12 > 10) # Evict "a" (LRU, size=3) -> total size = 4 # Now add "c" -> total size = 9 # Cache: {"b": (2, 4), "c": (3, 5)}

cache.get("a") # Returns -1 (evicted) cache.get("b") # Returns 2 (marks "b" as recently used)

cache.put("d", 4, 3) # Would exceed (9 + 3 = 12 > 10) # Evict "c" (LRU, size=5) -> total size = 4 # Add "d" -> total size = 7 # Cache: {"b": (2, 4), "d": (4, 3)} `

Requirements

• get(key): Retrieve value and mark as recently used, return -1 if not found
• put(key, value, size): Insert or update, evicting LRU items if needed
• Track total size separately from number of items
• Use O(1) operations for both get and put (amortized)

Clarification Questions to Ask

• Should get() update the item's access time (making it "most recently used")?
• Can an item's size change when updating an existing key?
• What should happen if a single item's size exceeds the total capacity?
• Are sizes guaranteed to be positive integers?
• Should the cache handle concurrent access?

Part 2: Handling Edge Cases

Extend your implementation to handle various edge cases that occur in production systems.

Edge Case 1: Item Larger Than Capacity

` cache = WeightedLRUCache(10) cache.put("huge", 1, 15) # Size 15 > capacity 10

Options:

1. Raise ValueError (recommended for clarity)

2. Clear cache and don't insert

3. Allow it and adjust capacity (not recommended)

`

Edge Case 2: Update Existing Key with Different Size

cache = WeightedLRUCache(10) cache.put("a", 1, 3) # Total size = 3 cache.put("a", 100, 8) # Same key, different size # Total size changes from 3 to 8 cache.get("a") # Returns 100

Edge Case 3: Multiple Evictions

cache = WeightedLRUCache(10) cache.put("a", 1, 3) cache.put("b", 2, 3) cache.put("c", 3, 3) # Total = 9 cache.put("d", 4, 8) # Needs to evict multiple items # Must evict "a", "b", and "c" to fit "d"

Requirements

• Define and document behavior for each edge case
• Handle updates to existing keys efficiently (adjust total size correctly)
• Evict multiple items if necessary to make room for a new item
• Validate inputs (positive sizes, valid capacity)

Part 3: Optimized Implementation

For production use, optimize to achieve O(1) time complexity for both get and put operations.

Data Structure Choice

Use OrderedDict from Python's collections module:

• Maintains insertion order
• Provides O(1) access, insertion, and deletion
• move_to_end(key) moves an item to the end in O(1) time
• popitem(last=False) removes from the front (LRU end) in O(1) time

Example

` from collections import OrderedDict

cache = OrderedDict() # key -> (value, size)

On get: move_to_end(key) to mark as recently used

On put: popitem(last=False) to evict LRU item

`

Requirements

• get() should be O(1)
• put() should be O(1) amortized (worst case involves evicting k items = O(k))
• Efficiently track both key-value mappings and LRU ordering
• Maintain accurate total size tracking