FastPrepLFU Cache
Problems/LFU Cache

LFU Cache

Zomato / Eternal logoZomato / Eternal● HardFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report names LFU-cache pseudocode and an LRU discussion but leaves out the operation rules and the tie rules. Our version is about 80% the same as the reported question.

Implement a least-frequently-used cache with positive integer capacity. Process each command in operations in order:

  • put key value inserts a new key or updates an existing key.
  • get key returns the stored value, or -1 when 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 <= 10000
  • 1 <= operations.length <= 200000
  • Each operation is exactly get key or put 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
All Zomato / Eternal interview questionsSee Zomato / Eternal hiring insights
Saved
class Solution {
    public int[] processLfuCache(int capacity, String[] operations) {
      // write your code here
    }
}
Checking account…