FastPrepWeighted LFU Cache
Problems/Weighted LFU Cache

Weighted LFU Cache

Microsoft logoMicrosoft● HardFULLTIMEOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: The visible source defines weighted capacity and the main PUT, GET, and PEEK behavior but cuts off the explicit eviction ordering, 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.
  • 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.

More Microsoft problems

  • Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
  • Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
  • Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public int[] processWeightedLfuCache(int capacity, String[] queries) {
        // Write your code here.
    }

}
Checking account…