How should I practice Weighted LFU Cache?

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

Is Weighted LFU Cache associated with IMC?

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

Problem · Hash Table

Weighted LFU Cache

Learn this problem

● HardIMIMCINTERNNEW GRADOA

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.

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 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","GET 1","PUT 3 300 5","GET 2","GET 3"]return = [100,-1,300]

The first GET raises key 1 to frequency 2. Inserting key 3 makes the total size 13, so key 2 is evicted before key 3 because both have frequency 1 and key 2 is less recent.

Example 2

capacity = 5queries = ["PUT 1 10 2","GET 1","PUT 2 20 3","PUT 1 11 4","PUT 1 99 6","GET 1","GET 2"]return = [10,11,-1]

Updating key 1 keeps its frequency at 2 and increases its size, so key 2 is evicted. The later update with size 6 is ignored because it exceeds capacity, leaving value 11 unchanged.

Constraints

1 <= capacity <= 10^9
1 <= queries.length <= 2 * 10^5
Every query is exactly GET 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.