Weighted Cache Eviction (Weight-Constrained Cache)

Problem: Weighted Cache Eviction (Weight-Constrained Cache) Design and implement a cache WeightedCache with a total weight capacity constraint. Each cache entry has: key value weight (a positive integer) Given capacity, the sum of weights of all cached entries must not exceed capacity. If an insert/update makes the total weight exceed capacity, evict entries as follows: Repeatedly evict the entry with the largest weight until the total weight is within capacity. If multiple entries share the same maximum weight, any deterministic tie-breaking rule is acceptable. Supported operations: get(key) -> value Return the value if present, otherwise -1. put(key, value, weight) -> void If key exists, update its value and weight. Otherwise insert a new entry. After insert/update, evict as needed. If weight > capacity, the item cannot be cached (recommended behavior: ignore the put). Constraints / Expectations capacity >= 1 weight >= 1 Aim for efficient operations (e.g., close to O(log n)). Example capacity = 10 put(A, 1, 6) -> {A(6)} total 6 put(B, 2, 5) -> total 11, evict heaviest A(6), remaining {B(5)} get(A) -> -1 get(B) -> 2 I/O Format for Testing Line 1: capacity Line 2: q number of operations Next q lines: PUT key value weight GET key Print one line per GET. Example Input 10 7 PUT A 1 6 PUT B 2 5 GET A GET B PUT C 3 4 GET C GET B Output -1 2 3 2