How should I practice LFU Cache?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Goldman Sachs phone screen problems in FastPrep.

Is LFU Cache associated with Goldman Sachs?

FastPrep tags this as a Goldman Sachs phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Design

LFU Cache

Learn this problem

● Hard

Goldman SachsFULLTIMEPHONE SCREEN

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.
remove key deletes the key when present and otherwise has no effect.

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 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 10","put 2 20","get 1","remove 1","get 1","put 3 30","get 2","get 3"]return = [10,-1,20,30]

Reading key 1 returns 10. Removing it makes the next read miss. Keys 2 and 3 then remain in the two-entry cache.

Example 2

capacity = 2operations = ["put 1 1","put 2 2","get 1","put 3 3","remove 1","get 1","get 3"]return = [1,-1,3]

The read raises key 1 above key 2, so inserting key 3 evicts key 2. Removing key 1 makes the later read miss.

Constraints

1 <= capacity <= 10000.
1 <= operations.length <= 200000.
Each operation is exactly get key, put key value, or remove key.
Every key and value fits in a signed 32-bit integer.