LFU Cache
Updated
Problem statement
Implement a least-frequently-used cache with positive integer capacity. Process each command in operations in order:
put key valueinserts a new key or updates an existing key.get keyreturns the stored value, or-1when the key is absent.
A successful get and a put that updates an existing key each increase that key's access frequency by one and make it most recently used within its new frequency.
When insertion exceeds capacity, evict a key with the smallest frequency. If several keys share that frequency, evict the least recently used one. Return the results of the get commands in order.
Function
processLfuCache(capacity: int, operations: String[]) → int[]Examples
Example 1
capacity = 2operations = ["put 1 1","put 2 2","get 1","put 3 3","get 2","get 3","put 4 4","get 1","get 3","get 4"]return = [1,-1,3,-1,3,4]Reading key 1 raises its frequency, so key 2 is evicted when key 3 is inserted. Before key 4 is inserted, keys 1 and 3 have equal frequency, and key 1 is the least recently used of them.
Example 2
capacity = 1operations = ["put 7 5","put 7 8","get 7","put 9 4","get 7","get 9"]return = [8,-1,4]Updating key 7 changes its value to 8 and increases its frequency. Inserting key 9 into the one-entry cache then evicts key 7.
Constraints
1 <= capacity <= 100001 <= operations.length <= 200000- Each operation is exactly
get keyorput key value. - Every key and value fits in a signed 32-bit integer.
More Zomato / Eternal interview questions
- Find the Two Unique NumbersONSITE INTERVIEW · Seen Oct 2026
- Flipping MatrixONSITE INTERVIEW · Seen Oct 2026
- Jump Game IVONSITE INTERVIEW · Seen Oct 2026
- Special KeyboardONSITE INTERVIEW · Seen Jul 2026
- Friend Circles and Redundant ConnectionsPHONE SCREEN · Seen Sep 2026
- Maximum Production Within PowerOA · Seen Jul 2026
- Rearrange Songs by AuthorOA · Seen Jul 2026
- Robot Warehouse OptimizationOA · Seen Jul 2026
Similar questions at other companies
- LFU CacheAmazon · ONSITE INTERVIEW
- LFU CacheSnowflake · OA · ONSITE INTERVIEWSnowflake interview questions
- LRU Cache with TTLAutodesk · ONSITE INTERVIEWAutodesk interview questions
- Recover a Function-Call LRU Cache with a Write-Ahead LogAnthropic · ONSITE INTERVIEWAnthropic interview questions
- LFU CacheSalesforce · ONSITE INTERVIEWSalesforce interview questions
- LFU CacheBlinkit · ONSITE INTERVIEWBlinkit interview questions
- Fair Multi-Tenant CacheOkta · ONSITE INTERVIEWOkta interview questions
- LFU CachexAI · ONSITE INTERVIEWxAI interview questions
- Windowed Key-Value MapConfluent · PHONE SCREEN · ONSITE INTERVIEWConfluent interview questions
- Least Frequently Used CacheOnehouse · ONSITE INTERVIEW