hardHeap / Priority QueuePure DSA~50 min
Feature Flag LFU Cache
A feature-flag service caches flag evaluations. When the cache is full it should evict the least-frequently-used flag, breaking ties by evicting the one used least recently. Implement that cache.
Problem
Design an LFU cache supporting get(key) and put(key, value) in O(1) average time. On overflow, evict the least-frequently-used key; on a frequency tie, evict the least-recently-used among them. get returns −1 for a missing key.
Input
A capacity, then a sequence of get/put operations.
Output
For each get, the value or −1.
Constraints
- 0 ≤ capacity ≤ 10^4
- Up to 2·10^5 operations
- get and put must be O(1) average
Examples
Example 1
Input
cap=2; put(1,1); put(2,2); get(1)→1; put(3,3) evicts 2; get(2)→-1; get(3)→3
Output
[1, -1, 3]
Key 1 had higher frequency than 2, so 2 was evicted when 3 was inserted.
Example 2
Input
cap=0; put(0,0); get(0)→-1
Output
[-1]
A zero-capacity cache stores nothing.