LFU Cache with Thread-Safety Follow-Up
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. A newly inserted key starts with frequency one.
When insertion would exceed capacity, first 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.
Example 3
capacity = 2operations = ["put 1 10","put 2 20","put 1 11","put 3 30","get 1","get 2","get 3"]return = [11,-1,30]Updating key 1 raises its frequency to two. Key 2 remains at frequency one and is evicted when key 3 is inserted.
Constraints
1 <= capacity <= 10^41 <= operations.length <= 2 * 10^5- Every operation is exactly
get keyorput key value. - Every key and value fits in a signed 32-bit integer.
- At least one operation is
get.
More Confluent Onsite Interview questions
- Implement tail -nPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Sudoku Board ValidationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Sudoku Puzzle SolverPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Sequential Phrase Search Across DocumentsPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Bounded Combination Sum with Signed CandidatesONSITE INTERVIEW · Seen Oct 2026
- Detect a Silent SensorONSITE INTERVIEW · Seen Sep 2026
- Build an Inverted Document IndexONSITE INTERVIEW · Seen Sep 2026
- Combination Sum with Unlimited ReuseONSITE INTERVIEW · Seen Sep 2026
- Word Search Across DocumentsPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Windowed Key-Value MapPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2025
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 CacheZomato / Eternal · ONSITE INTERVIEWZomato / Eternal interview questions
- LFU CachexAI · ONSITE INTERVIEWxAI interview questions
- Least Frequently Used CacheOnehouse · ONSITE INTERVIEW