Design a Weighted Cache (Phone Screen)

Implement a weighted cache WeightedCache<K,V>. APIs get(K key) -> V | null put(K key, V value, int weight) -> void Constraints The cache has a maximum capacity maxWeight measured by the sum of weights. If inserting/updating makes the total weight exceed maxWeight, evict entries according to a chosen policy until the constraint holds. Notes Explain your eviction policy (e.g., LRU/LFU/custom) and how updates to an existing key affect total weight. Discuss time complexity. Scale assumptions 0 < maxWeight <= 1e9 Up to 1e5 operations. Example maxWeight = 10 put(a,1,6), put(b,2,5) exceeds the limit; evict entries to make total weight <= 10. Example Input maxWeight=10 put a 1 6 put b 2 5 get a get b Output implementation-dependent (based on eviction policy)