FastPrepWeighted LFU Cache
Problems/Weighted LFU Cache

Weighted LFU Cache

IMC Trading logoIMC Trading● HardINTERNNEW GRADOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: The visible source defines weighted capacity and the main PUT/GET behavior but cuts off part of the access and eviction rules, the runner interface, examples, and bounds. The judged core task matches the visible source at about 88%.

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.

More IMC Trading problems

  • Earliest Meeting Start on a 24-Hour ClockOA · Seen Nov 2026
  • Grid Paths with Override PassesOA · Seen Oct 2026
  • Pro-Rata Order BookONSITE INTERVIEW · Seen Sep 2026
All IMC Trading interview questionsSee IMC Trading hiring insights
Saved
class Solution {
    public int[] processWeightedLfuCache(int capacity, String[] queries) {
        // Write your code here.
    }

}
Checking account…