Implement an LFU Cache with LRU Tie-Breaking

Implement a least-frequently-used cache. get(key) returns its value or -1 when absent. put(key,value) inserts or updates an entry. New entries start with frequency one; a successful get or an update through put increments the entry's frequency. When inserting into a full cache, evict the lowest-frequency key, breaking ties by least recent use. Both operations should take O(1) average time. ### Constraints and Clarifications The report explicitly recognizes the named LFU problem. Use the [official LFU Cache reference](https://leetcode.com/problems/lfu-cache/description/) for this practice contract: capacity 1–10000, keys 0–100000, values 0–1000000000, and at most 200000 operations. These are reference-context constraints, not independently reported interview bounds. A missing get changes nothing. Serialized construction and put operations emit null; get emits its integer result. ### What a Strong Answer Covers Maintain key lookup, frequency buckets ordered by recency, and the current minimum frequency. Explain promotions, updates, and tie-breaking without scanning all keys. ### Follow-up Questions - Why does moving the last key out of the minimum-frequency bucket allow a simple minimum update? - Why must an update to an existing key avoid evicting another entry?