How should I practice LFU Cache?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Zomato / Eternal onsite interview problems in FastPrep.

Is LFU Cache associated with Zomato / Eternal?

FastPrep tags this as a Zomato / Eternal onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Design

LFU Cache

Learn this problem

● Hard

Zomato / EternalFULLTIMEONSITE INTERVIEW

Problem statement

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.