Least Frequently Used Cache
Reported by candidates from Onehouse's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Onehouse reported this one in November 2023: build a least-frequently-used cache and replay a list of get and put commands. It looks like a standard LFU design question until a put on an existing key hits a full cache. That's the edge case that breaks the naive version. If you evict before checking whether the key already exists, you throw away a good entry and corrupt the answer. You've probably seen LFU before, but the OA wants it exact, with ties broken by recency. If you blank on the structure mid-assessment, StealthCoder is the safety net running invisibly on your screen.
The problem
Implement a least-frequently-used cache with positive integer capacity. Process each command in operations in order: put key value inserts a new key or updates an existing key. get key returns the stored value, or -1 when the key is absent. A successful get and a put that updates an existing key each increase that key's access frequency by one and make it most recently used within its new frequency. A newly inserted key starts with frequency one. When insertion would exceed capacity, first evict a key with the smallest frequency. If several keys share that frequency, evict the least recently used one. Return the results of the get commands in order. Function processLfuCache(capacity: int, operations: String[]) → int[] Examples Example 1 capacity = 2 operations = ["put 1 1","put 2 2","get 1","put 3 3","get 2","get 3","put 4 4","get 1","get 3","get 4"] return = [1,-1,3,-1,3,4] Reading key 1 raises its frequency, so key 2 is evicted when key 3 is inserted. Before key 4 is inserted, keys 1 and 3 have equal frequency, and key 1 is the least recently used of them. Example 2 capacity = 1 operations = ["put 7 5","put 7 8","get 7","put 9 4","get 7","get 9"] return = [8,-1,4] Updating key 7 changes its value to 8 and increases its frequency. Inserting key 9 into the one-entry cache then evicts key 7. Example 3 capacity = 2 operations = ["put 1 10","put 2 20","put 1 11","put 3 30","get 1","get 2","get 3"] return = [11,-1,30] Updating key 1 raises its frequency to two. Key 2 remains at frequency one and is evicted when key 3 is inserted. Constraints 1 <= capacity <= 10^4 1 <= operations.length <= 2 * 10^5 Every operation is exactly get key or put key value. Every key and value fits in a signed 32-bit integer. At least one operation is get.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is O(1) per operation. Keep a map from key to value and frequency, a map from frequency to an ordered set of keys (a linked hash map works well), and a running minFreq. On get or an updating put, move the key from its frequency bucket to freq+1 and append it as most recent. If the old bucket empties and it was minFreq, bump minFreq. On a new put at capacity, evict the oldest key in the minFreq bucket, then insert with frequency 1 and set minFreq to 1. The pitfalls: an update must never trigger eviction, and a put that updates counts as an access. With up to 2*10^5 operations, a scan for the minimum frequency will time out. If the bucket bookkeeping slips live, StealthCoder can give you the reference structure as a hedge.
If this hits your live OA and you blank, StealthCoder solves it in seconds, invisible to the proctor.
You can drill Least Frequently Used 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 by an Amazon engineer who would have shipped this the night before his JPMorgan OA if he'd had it.
Get StealthCoderRelated leaked OAs
This OA pattern shows up on LeetCode as lfu cache. If you have time before the OA, drill that.
You've seen the question.
Make sure you actually pass Onehouse's OA.
Onehouse reuses patterns across OAs. Built by an Amazon engineer who would have shipped this the night before his JPMorgan OA if he'd had it. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Least Frequently Used Cache FAQ
What's the trick to the Onehouse LFU cache problem?+
Use a frequency-to-ordered-keys map plus a minFreq pointer. Every get and updating put moves a key up one bucket. Eviction pops the oldest key from the minFreq bucket. That gives O(1) per operation, which you need for 2*10^5 operations.
What edge case breaks a naive solution?+
Calling put on an existing key when the cache is full. You must update the value and bump frequency without evicting anything. Evicting first removes a key you were about to update. Example 2 with capacity 1 and a repeated put on key 7 tests exactly this.
How do ties get broken between keys with the same frequency?+
The least recently used key in that frequency bucket goes first. Every access moves a key to the most recent end of its new bucket. In Example 1, keys 1 and 3 tie at frequency two, and key 1 is older, so it gets evicted.
Does a failed get change anything?+
No. A get on a missing key returns -1 and touches nothing. Only a successful get or a put that updates an existing key raises frequency. A new key starts at frequency one, and minFreq resets to 1 on insertion.
How do I prepare for this in 48 hours?+
Write the LFU cache from scratch twice without notes. Use a hash map of keys plus a map of frequency to ordered key sets. Then trace the three examples by hand, focusing on minFreq updates and the full-cache update case. Parsing the operation strings is the easy part.