How should I practice LFU Cache?

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

Is LFU Cache associated with Snowflake?

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

LFU Cache

Snowflake● HardFULLTIMEONSITE INTERVIEW

Problem statement

Run a list of operations on an empty least-frequently-used (LFU) cache that holds at most capacity keys. Return the results of all get operations, in order.

[0, key] is a get. If the key is in the cache, the result is its value. If not, the result is -1, and nothing in the cache changes.
[1, key, value] is a put. If the key is in the cache, replace its value. If not, add it.

Each key has a frequency. A new key starts at 1, and adding it counts as its most recent use. A get that finds the key and a put on an existing key each add 1 to its frequency, and both count as a use of that key.

When a put adds a new key to a full cache, first remove one key: the one with the lowest frequency. If several keys tie, remove the one used least recently. A removed key is forgotten, so if it is added again it starts over at frequency 1. A put on an existing key never removes anything.

Try for average O(1) time per operation. The tests do not enforce this, and with these limits a slower scan also passes.

Function

runLfuCache(capacity: int, operations: int[][]) → int[]

Examples

Example 1

capacity = 2operations = [[1,1,10],[1,2,20],[0,1],[1,3,30],[0,2],[0,3]]return = [10,-1,30]

Keys 1 and 2 start with frequency 1. The get on key 1 returns 10 and raises its frequency to 2. Adding key 3 finds the cache full, so key 2 is removed because it has the lowest frequency. Then key 2 returns -1 and key 3 returns 30.

Example 2

capacity = 2operations = [[1,1,10],[1,2,20],[0,1],[0,2],[1,3,30],[0,1],[0,2],[0,3]]return = [10,20,-1,20,30]

After both gets, keys 1 and 2 tie at frequency 2. Key 1 was used less recently, so adding key 3 removes it. The last three gets return -1, 20 and 30.

Example 3

capacity = 2operations = [[1,1,10],[1,2,20],[1,1,11],[1,3,30],[0,1],[0,2]]return = [11,-1]

Writing to existing key 1 replaces its value and raises its frequency to 2, and nothing is removed. Adding key 3 then removes key 2. The gets return 11 and -1.

Example 4

capacity = 2operations = [[1,1,10],[1,2,20],[1,3,30],[0,1],[0,2],[0,3]]return = [-1,20,30]

Keys 1 and 2 tie at frequency 1. Adding a key counts as its most recent use, so key 1 is the less recent, and adding key 3 removes it. The gets return -1, 20 and 30.

Constraints

1 <= capacity <= 5000
1 <= operations.length <= 5000
Each operation is exactly [0, key] or [1, key, value].
0 <= key, value <= 10^9