Design a Weighted Cache (Weighted LRU Cache)

Problem: Design a Weighted Cache (Weighted LRU Cache) Implement a cache data structure WeightedCache. Each cache entry has: key: string value: string (or any object; use strings for simplicity) weight: a positive integer representing the entry's size/weight The cache has a maximum capacity (positive integer) that limits the sum of weights of all entries. Operations put(key, value, weight) If weight > capacity, the item can never fit; keep the cache unchanged (or throw—state your choice). If key already exists, update its value and weight, and mark it as most recently used. If after insert/update the total weight exceeds capacity, evict entries by LRU (Least Recently Used) order (from least recently used onward) until total weight <= capacity. get(key) If present, return the value and mark the entry as most recently used. Otherwise return empty (e.g., null / -1). (Optional) currentWeight() Return the current total weight. Expected Complexity Average O(1) for both get and put. Example capacity = 10 put(A, "a", 6) -> {A}, total=6 put(B, "b", 4) -> {A,B}, total=10 get(A) -> returns "a", A becomes most recently used put(C, "c", 5) -> total would be 15; evict LRU (B) -> total=11 still too big; evict next (A) -> total=5; final cache {C} Note: If the original question uses a different API or eviction policy, follow the interviewer’s spec. This is the most common “weight-based capacity + LRU eviction” weighted cache variant. Example Input 10 put A a 6 put B b 4 get A put C c 5 get B get A get C Output a None None c