Hey r/DarkInterview — sharing a free xAI coding question from https://darkinterview.com .

---

Weighted LRU Cache

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 — image caching, API response caching, database query result caching, etc.

---

Part 1: Basic Implementation

Implement a WeightedLRUCache class with two core operations:

1. get(key): Retrieve the value associated with the key. Returns -1 if the key doesn't exist.
2. put(key, value, size): Insert or update a key-value pair with an associated size. If adding the item causes the total size to exceed capacity, evict the least recently used items until there's enough space.

Example

`python

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)} `

---

Part 2: Edge Cases (Important!!)

Extend your implementation to handle production edge cases:

1. Item larger than capacity — what if a single item's size exceeds the total capacity? Raise an error? Silently skip? Clear the cache?
2. Update existing key with different size — put() called with an existing key but a different size. Must adjust total correctly.
3. Multiple evictions — adding one item may require evicting several existing items.
4. Zero-size items — should they be allowed?

Example

`python cache = WeightedLRUCache(10)

Multiple evictions

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 "a", "b", AND "c" to fit "d" `

---

Part 3: Optimize to O(1)

Optimize your implementation so that both get() and put() run in O(1) time.

Hint: Think about what data structures give you O(1) lookup and O(1) ordered insertion/removal.

| Operation | Target Complexity | Notes | |---|---|---| | get() | O(1) | HashMap lookup + linked list reorder | | put() (no eviction) | O(1) | HashMap insert + linked list append | | put() (with k evictions) | O(k) | Must evict k items |

---

Key Design Decisions to Discuss

• Size estimation: How do you accurately measure item size in memory? Should metadata overhead be included?
• Item exceeds capacity: What's the right behavior — raise error, skip, or clear and insert?
• Comparison to standard LRU: When does the weighted variant matter vs. a simple item-count LRU?

---

Follow-up Discussion Topics

The interviewer may ask you to extend the design verbally:

1. Thread safety — how would you make this concurrent? Read-write locks for read-heavy workloads? Lock-free data structures?
2. TTL (Time-To-Live) — extend the cache to support item expiration. How do you combine LRU eviction with TTL-based eviction?
3. Monitoring — what metrics would you track in production? (hit rate, eviction rate, capacity utilization)
4. Alternative eviction policies — Weighted LFU: evict items with the lowest (frequency / size) ratio instead of recency. When is this better?

---

Full question + Python solution with Doubly Linked List + HashMap implementation: https://darkinterview.com/collections/m5n8v3x1/questions/4d7c77cc-58d1-4334-9322-a034c2c0d19a