Least Recently Used Cache
Reported by candidates from Onehouse's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The Onehouse OA, reported in November 2023, hands you an LRU cache and a string array of operations, and the naive version quietly breaks on one case. It's the classic design problem, but wrapped in a function you have to parse yourself: runLRU(capacity, operations) returns only the GET results. If you've seen LRU before, you'll feel safe. That's the trap. Updating an existing key, missing GETs, and a stored value of 0 all behave differently than you'd assume. Nail those and it's a ten-minute problem. If you blank on the linked-list wiring during the live OA, StealthCoder runs invisibly as a safety net and gives you the structure in real time.
The problem
Process a sequence of operations on a least recently used cache with capacity capacity. PUT key value inserts or updates a key. An update makes the key most recently used. If a new insertion exceeds capacity, evict the least recently used key. GET key returns the stored value, or -1 when the key is absent. A hit makes the key most recently used; a miss does not change recency. Return all GET results in operation order. Operation fields are decimal integers separated by one space. Function runLRU(capacity: int, operations: String[]) → int[] Examples Example 1 capacity = 2 operations = ["PUT 1 10","PUT 2 20","GET 1","PUT 3 30","GET 2","GET 3"] return = [10,-1,30] The lookup of key 1 makes key 2 least recently used, so inserting key 3 evicts key 2. Example 2 capacity = 1 operations = ["PUT 5 7","PUT 5 9","GET 5","PUT 6 4","GET 5"] return = [9,-1] Updating key 5 replaces its value without adding a second entry. Inserting key 6 later evicts it. Example 3 capacity = 3 operations = ["GET 8","PUT 8 0","GET 8"] return = [-1,0] The first lookup misses. After insertion, a stored value of 0 is returned normally. Constraints 1 <= capacity <= 10^5 1 <= operations.length <= 2 * 10^5 Every operation is exactly GET key or PUT key value. -10^9 <= key, value <= 10^9
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is a hash map plus a doubly linked list, so GET and PUT both run in O(1). The map points from key to node. The list orders nodes by recency, with head as most recent and tail as least recent. On a GET hit, move the node to the front. On a miss, change nothing and append -1. On a PUT of an existing key, update the value and move it to the front without growing size. Only evict when a brand new key pushes you past capacity. Pitfalls: treating 0 as falsy and reporting a miss, evicting on an update, and forgetting that misses don't touch recency. Keys and values can be negative, so don't use them as array indexes. Parse each string by splitting on a space. In a language with an ordered map, you can shortcut. If the pointer logic slips under pressure, StealthCoder is the hedge on the live OA.
Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.
You can drill Least Recently 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. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge.
Get StealthCoderRelated leaked OAs
This OA pattern shows up on LeetCode as lru 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. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Least Recently Used Cache FAQ
What's the trick to the Onehouse LRU cache problem?+
Pair a hash map with a doubly linked list so every operation is O(1). The map finds the node, the list tracks recency. Move a node to the front on every hit or update, and evict from the tail only when a new key overflows capacity.
What edge case breaks a naive solution here?+
Updating an existing key. A naive version counts it as a new insertion and evicts something, or leaves recency unchanged. An update must replace the value, move the key to most recent, and never change size. Also watch stored values of 0, which are valid hits.
Does a GET miss change the cache order?+
No. The problem says a miss does not change recency. You just append -1 to the results and move on. Only a hit promotes the key to most recently used, so don't insert placeholder entries on misses.
Can I use a built-in ordered map instead of writing a linked list?+
The problem doesn't forbid it, so an ordered dictionary or linked hash map works if your language has one. Be ready to explain the O(1) reasoning anyway. If you're unsure of the built-in's move-to-end behavior, write the linked list by hand.
How do I prepare for this in 48 hours?+
Write the LRU cache from scratch twice without looking. Use sentinel head and tail nodes to kill null checks. Then add the string parsing layer: split each operation on a space, convert to integers, and collect only GET outputs. Test the three examples, including capacity 1.