Weighted LRU Cache

An LRU cache variant where each entry carries a size/weight and the cache is bounded by total size rather than item count, so one insertion may evict several least-recently-used entries. Asked inside a short screen and reported as time-tight. Problem Build a Weighted LRU cache. Unlike a classic LRU that caps the count of entries, every item carries a size (weight) and the cache is full when the total size of live items would exceed capacity. A single insertion may therefore evict several least-recently-used items to make room. class WeightedLRUCache: def __init__(self, capacity: int): ... # capacity = max total size, not item count def get(self, key: str) -> int: ... # value, or -1 if absent; marks the key most-recently-used def put(self, key: str, value: int, size: int) -> None: ... # insert or update; if total size would exceed capacity, evict LRU items until it fits. Examples cache = WeightedLRUCache(capacity=10) cache.put("a", 1, 3) # total = 3 cache.put("b", 2, 4) # total = 7 cache.put("c", 3, 5) # 7+5 > 10 -> evict "a" (LRU) -> total = 4, then add "c" -> total = 9 cache.get("a") # -1 (evicted) cache.get("b") # 2 (now most-recently-used) cache.put("d", 4, 3) # 9+3 > 10 -> evict "c" (LRU) -> add "d" -> total = 7 Notes Target O(1) get and amortized O(1) put with a hashmap + doubly-linked list (the LC 146 structure): get and every put move the touched node to the MRU end; eviction pops from the LRU end. OrderedDict with move_to_end / popitem(last=False) is the shortcut implementation. Track current_size incrementally; when updating an existing key, subtract its old size before adding the new size so the running total stays correct. Eviction is a while current_size + size > capacity: evict_lru() loop — one insert can evict multiple items, unlike classic LRU which evicts at most one. Edge cases to clarify and handle explicitly: an item larger than the whole capacity (raise vs. ignore vs. clear), a size change on update of an existing key, size 0 / negative, and an exact-fit insertion. Likely follow-ups: thread-safety (lock around the critical section), TTL expiry layered on top, and weighted-LFU (evict by lowest frequency-per-size score) as an alternative eviction policy. Preparation Write the OrderedDict version first (fits in ~10 minutes), then the explicit Node + dummy-head/tail doubly-linked-list version for the O(1) follow-up. Be ready to state the eviction invariant and walk the multi-eviction example by hand. Reported as time-tight inside a short screen — get a correct simple version down before optimizing.