Least Frequently Used Cache
NVIDIA● HardFULLTIMEPHONE SCREENProblem statement
Implement an initially empty least-frequently-used cache with capacity capacity. Process each string in operations in order:
put key valueinserts a new key or updates its value. A new key starts with frequency 1. Updating a stored key increases its frequency by 1.get keyreturns its value and increases its frequency by 1 when present. Return-1when absent; a miss changes no stored frequency.
Before inserting a new key into a full cache, evict the key with the smallest frequency. If frequencies tie, evict the least recently used key among them. Every successful get, update, and insertion makes that key most recently used within its frequency. A zero-capacity cache never stores anything.
Return the results of get operations in order. Each cache operation should take average O(1) time. The finite command list is the practice adapter for the cache interface.
Function
processLfuCache(capacity: int, operations: String[]) → int[]Examples
Example 1
capacity = 2operations = ["put 1 10","put 2 20","get 1","put 3 30","get 2","get 3","put 4 40","get 1","get 3","get 4"]return = [10,-1,30,-1,30,40]Reading key 1 protects it from the first eviction. Before inserting key 4, keys 1 and 3 tie at frequency 2; key 1 is less recent and is evicted.
Example 2
capacity = 0operations = ["put 5 50","get 5"]return = [-1]With zero capacity, the put stores no entry.
Constraints
- For this exercise, assume
0 <= capacity <= 100000and0 <= operations.length <= 100000. - For this exercise, assume keys and values are integers in
[0, 10^9]. - Each command is exactly
put key valueorget key, with single spaces and valid integers.