Weighted LFU Cache
Reported by candidates from IMC's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The mistake that sinks a first attempt at IMC's Weighted LFU Cache, reported in August 2026, is treating it like the classic LFU where you evict exactly one entry. Here sizes vary, so one PUT can force several evictions, and the entry you just inserted can be the one that gets kicked out. It's a design problem with 2 * 10^5 queries, so every operation needs to be near O(1) or O(log n). If you've seen LeetCode's LFU Cache, you're halfway there. If you blank on the bookkeeping, StealthCoder sits invisibly on your screen as a safety net during the live OA.
The problem
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 = 10 queries = ["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 = 5 queries = ["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.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is the classic LFU structure with a size counter bolted on. Keep a map from key to entry (value, size, freq), plus a map from frequency to an ordered list of keys, oldest first, and track minFreq. GET bumps freq and moves the key to the tail of the new bucket. PUT on an existing key updates value and size, keeps freq, and refreshes recency in the same bucket. After every accepted PUT, loop while totalSize > capacity: pop the head of the minFreq bucket, subtract its size. The pitfalls: rejecting size > capacity before touching anything, forgetting to subtract the old size on an update, not recomputing minFreq after evicting the last key in a bucket, and excluding the just-inserted key from eviction. It must be eligible. Use 64-bit for total size, since sizes reach 10^9. StealthCoder is the hedge if the bucket bookkeeping falls apart mid-assessment.
The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.
You can drill Weighted LFU Cache cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass IMC's OA.
IMC reuses patterns across OAs. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Weighted LFU Cache FAQ
What's the core trick in Weighted LFU Cache?+
Use LFU with frequency buckets, each an insertion-ordered list, and a running total of sizes. After each accepted PUT, evict from the lowest-frequency bucket's oldest entry in a loop until total size fits capacity. The loop is the main difference from standard LFU.
Can the key I just inserted get evicted?+
Yes. The problem says eviction considers every current entry, including the key just inserted or updated. A new key sits at frequency 1, so if it's the least recent among the lowest frequency, it can be removed right away. Don't special-case it.
What happens when a PUT size is larger than capacity?+
Ignore the whole operation. The cache stays unchanged, including any existing value, size, and frequency for that key. Example 2 shows this: the PUT with size 6 and capacity 5 leaves key 1 at value 11.
Does updating an existing key change its frequency?+
No. A PUT on an existing key updates value and size, keeps the frequency, and marks it most recent within that frequency. Only GET increments frequency. Mixing these up is the most common wrong answer on the examples.
How do I prepare for this in 48 hours?+
Write standard LFU from memory using a key map, frequency-to-ordered-set map, and minFreq. Then add the size total, the eviction loop, and the oversize check. Test both examples by hand. Use 64-bit integers for the total, since sizes go up to 10^9.