Implement a fixed-capacity Least-Frequently-Used cache, breaking ties by least-recently-used among the least-frequent keys.
Implement an LFU (Least Frequently Used) cache with a fixed capacity, set once at startup. Process commands from stdin, one per line.
Commands:
- INIT <capacity> : always the first line; sets capacity (>= 1).
- PUT <key> <value> : insert or update. On a new key when the cache is full, evict one entry first (see eviction rule). On an existing key, update its value.
- GET <key> : print the stored value, or -1 if the key is absent.
- SIZE : print the current number of entries.
Frequency rules:
- A new key enters with frequency 1.
- A successful GET increments that key's frequency.
- A PUT on an existing key updates its value AND increments its frequency (an update counts as a use).
- A GET on an absent key returns -1 and changes nothing.
Eviction rule (applied when a PUT of a NEW key would exceed capacity):
- Among all keys with the minimum frequency, evict the LEAST RECENTLY USED one : where "used" means the most recent GET or PUT that touched that key.
- Whenever a key's frequency increases, it becomes the most recently used key within its new frequency level.