How should I practice Weighted LFU Cache?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft online assessment problems in FastPrep.

Is Weighted LFU Cache associated with Microsoft?

FastPrep tags this as a Microsoft online assessment coding practice problem when the problem catalog has that company and stage context.

Weighted LFU Cache

Microsoft● HardFULLTIMEOA

Learn

Problem statement

Implement a Weighted Least Frequently Used (LFU) Cache with total capacity capacity. Every cached entry has an integer key, integer value, positive integer size, access frequency, and recency. The sum of the sizes of all cached entries must never exceed capacity.

Process the strings in queries in order. Each query has one of these forms:

PUT key value size: insert or update an entry. If size > capacity, ignore the entire operation and leave the cache unchanged. For an existing key, update its value and size without changing its frequency, and mark it as most recently accessed within that frequency. For a new key, insert it with frequency 1 and make it the most recent entry at that frequency.
GET key: if the key is absent, append -1 to the result. Otherwise, append its value, increment its frequency by 1, and make it the most recently accessed entry at the new frequency.
PEEK key: append the key's value when it exists, or -1 otherwise, without changing its frequency or recency.

After every accepted PUT, while the total stored size exceeds capacity, evict an entry with the smallest frequency. If several entries share that frequency, evict the least recently accessed one. The eviction policy considers every current entry, including the key just inserted or updated.

Return the results of all GET and PEEK queries in their original order.

Function

processWeightedLfuCache(capacity: int, queries: String[]) → int[]

Examples

Example 1

capacity = 10queries = ["PUT 1 100 4","PUT 2 200 4","PEEK 1","GET 1","PUT 3 300 5","PEEK 2","GET 2","PEEK 3"]return = [100,100,-1,-1,300]

PEEK 1 returns 100 without changing state. GET 1 then raises key 1 to frequency 2. Inserting key 3 exceeds capacity, so key 2 is evicted as the least-recent entry among the keys with frequency 1.

Example 2

capacity = 5queries = ["PUT 1 10 2","PUT 2 20 2","PEEK 1","PUT 3 30 2","GET 1","GET 2","PEEK 3"]return = [10,-1,20,30]

PEEK 1 does not refresh recency. When key 3 is inserted, key 1 is still the least-recent entry among those with frequency 1, so it is evicted.

Constraints

1 <= capacity <= 10^9
1 <= queries.length <= 2 * 10^5
Every query is exactly GET key, PEEK key, or PUT key value size.
Every key and value fits in a signed 32-bit integer.
1 <= size <= 10^9 for every PUT query.